Evolutionary algorithms and density functional theory are applied to investigate the Ge-Se system under pressure. Binary crystalline compounds Ge2Se3 and Ge3Se4 with unconventional stoichiometries are predicted to be energetically and dynamically stable. Ge2Se3 with a space group of R3m(hR5) is predicted to become stable above 5 GPa and exhibit phase transitions at higher pressures. Ge3Se4 is found to become stable from 40 GPa with a body-centred cubic I4[combining macron]3d crystal structure. Moreover, the conventional GeSe compound is predicted to become unstable above 50 GPa. By calculating the electron localization function, we show that electrons become more delocalized in Ge2Se3 as pressure increases. On the basis of band structure and electron-phonon coupling computations, Ge2Se3 and Ge3Se4 are shown to be metallic and exhibit superconducting transitions at low temperatures.