A one-dimensional fermionic system, such as a superconducting wire, may host Majorana zero-energy edge modes (MZMs) at its edges when it is in the topological phase. MZMs provide a path to realising fault-tolerant quantum computation, and so are the focus of intense experimental and theoretical studies. However, given a Hamiltonian, determining whether MZMs exist is a daunting task as it relies on knowing the spectral properties of the Hamiltonian in the thermodynamic limit. The Kitaev chain is a paradigmatic non-interacting model that supports MZMs and the Hamiltonian can be fully diagonalised. However, for interacting models, the situation is far more complex. Here we consider a different classification of models, namely, ones with frustration-free Hamiltonians. Within this class of models, interacting and non-interacting systems are treated on an equal footing, and we identify exactly which Hamiltonians can realise MZMs.