We investigate the robustness of Majorana edge modes under disorder and interactions. We exploit a recently found mapping of the interacting Kitaev chain in the symmetric region (μ=0, t=Δ) to free fermions. Extending the exact solution to the disordered case allows us to calculate analytically the topological phase boundary for all interaction and disorder strengths, which has been thought to be only accessible numerically. We discover a regime in which moderate disorder in the interaction matrix elements enhances topological order well into the strongly interacting regime U>t. We also derive the explicit form of the many-body Majorana edge wave function, revealing how it is dressed by many-particle fluctuations from interactions. The qualitative features of our analytical results are valid beyond the fine-tuned integrable point, as expected from the robustness of topological order and as corroborated here by an exact diagonalization study of small systems.