We study the low-energy physics of a chain of Majorana fermions in the presence of interaction and disorder, emphasizing the difference between Majoranas and conventional (complex) fermions. While in the non-interacting limit both models are equivalent (in particular, belong to the same symmetry class BDI and flow towards the same infinite-randomness critical fixed point), their behavior differs drastically once interaction is added. Our density-matrix renormalization group calculations show that the complex-fermion chain remains at the non-interacting fixed point. On the other hand, the Majorana fermion chain experiences a spontaneous symmetry breaking and localizes for repulsive interaction. To explain the instability of the critical Majorana chain with respect to a combined effect of interaction and disorder, we consider interaction as perturbation to the infinite-randomness fixed point and calculate numerically two-wave function correlation functions that enter interaction matrix elements. The numerical results supported by analytical arguments exhibit a rich structure of critical eigenstate correlations. This allows us to identify a relevant interaction operator that drives the Majorana chain away from the infinite randomness fixed point. For the case of complex fermions, the interaction is irrelevant.