We show that one-dimensional electron systems in proximity of a superconductor that support Majorana edge states are extremely susceptible to electron-electron interactions. Strong interactions generically destroy the induced superconducting gap that stabilizes the Majorana edge states. For weak interactions, the renormalization of the gap is nonuniversal and allows for a regime, in which the Majorana edge states persist. We present strategies how this regime can be reached.