A series of new superconducting binary silicides and germanides have recently been synthesized under high-pressure high-temperature conditions. A representative member of this group, BaGe3, was theoretically investigated using evolutionary structure searches coupled with structural analogies in the pressure range from 1 atm to 250 GPa, where three new phases were discovered. At 1 atm, in addition to the synthesized P63/mmc phase, we predicted two new phases, I4/mmm and Amm2, to be dynamically stable. The Amm2 structure comprises Ge clusters and triangular prisms intercalated with Ba and Ge atoms, a unique structural motif unknown to this group. The I4/mmm structure has been previously synthesized in binary silicides and is calculated to be thermodynamically stable in BaGe3 between 15.6 and 35.4 GPa. Above 35.4 GPa, two new phases of P6̅m2 and R3̅m symmetry become the global minima and remain so up to the highest pressure considered. These two phases have very similar enthalpies, and both feature layers of double Kagome nets of Ge intercalated with Ba-Ge layers. The predicted phases are suggested to be metallic with itinerant electrons and to be potentially superconducting from the considerable electron-phonon coupling strength. Density functional perturbation calculations combined with the Allen-Dynes-modified McMillan formula were used to estimate the superconducting critical temperatures (Tc) for these new phases, which, with slight pressure variations, are comparable to the experimental Tc measured for the P63/mmc phase.