To predict all stable compounds in the Ba-C system, we perform a comprehensive study using first-principles variable-composition evolutionary algorithm USPEX. We find that at 0 K the well-known compound BaC2 is metastable in the whole pressure range 0-40 GPa, while intercalated graphite phase BaC6 is stable at 0-19 GPa. A hitherto unknown layered orthorhombic Pbam phase of BaC has structure consisting of alternating layers of Ba atoms and layers of stoichiometry Ba2C3 containing linear C3 groups and is predicted to be stable in the pressure range 3-32 GPa. From our electron-phonon coupling calculations, the newly found BaC compound is a phonon-mediated superconductor and has a critical superconductivity temperature Tc of 4.32 K at 5 GPa. This compound is dynamically stable at 0 GPa and therefore may be quenchable under normal conditions.