Recently, there has been substantial progress in methods of identifying local integrals of motion in interacting integrable models or in systems with many-body localization. We show that one of these approaches can be utilized for constructing local, conserved, Majorana fermions in systems with an arbitrary many-body interaction. As a test case, we first investigate a noninteracting Kitaev model and demonstrate that this approach perfectly reproduces the standard results. Then, we discuss how the many-body interactions influence the spatial structure and the lifetime of the Majorana modes. Finally, we determine the regime for which the information stored in the Majorana correlators is also retained for arbitrarily long times at high temperatures. We show that it is included in the regime with topologically protected soft Majorana modes, but in some cases is significantly smaller.