The HI Parkes All-Sky Survey (HIPASS) is a blind 21cm survey for extragalactic neutral hydrogen, covering the whole southern sky. The HIPASS Bright Galaxy Catalog (BGC) is a subset of HIPASS and contains the 1000 HI brightest (peak flux density) galaxies. Here we present the 138 HIPASS BGC galaxies that had no redshift measured prior to the Parkes multibeam HI surveys. Of the 138 galaxies, 87 are newly catalogued. Newly catalogued is defined as having no optical (or infrared) counterpart in the NASA/IPAC Extragalactic Database. Using the Digitized Sky Survey, we identify optical counterparts for almost half of the newly catalogued galaxies, which are typically of irregular or Magellanic morphological type. Several HI sources appear to be associated with compact groups or pairs of galaxies rather than an individual galaxy. The majority (57) of the newly catalogued galaxies lie within 10{deg} of the Galactic plane and are missing from optical surveys as a result of confusion with stars or dust extinction. This sample also includes newly catalogued galaxies first discovered by Henning et al. in the HI shallow survey of the zone of avoidance. The other 30 newly catalogued galaxies escaped detection because of their low surface brightness or optical compactness. Only one of these, HIPASS J0546-68, has no obvious optical counterpart, as it is obscured by the Large Magellanic Cloud. We find that the newly catalogued galaxies with |b|>10{deg} are generally lower in HI mass and narrower in velocity width compared with the total HIPASS BGC. In contrast, newly catalogued galaxies behind the Milky Way are found to be statistically similar to the entire HIPASS BGC. In addition to these galaxies, the HIPASS BGC contains four previously unknown HI clouds. Description: