The pseudofermion functional renormalization group (PFFRG) method has proven to be a powerful numerical approach to treat frustrated quantum spin systems. In its usual implementation, however, the complex fermionic representation of spin operators introduces unphysical Hilbert-space sectors which render an application at finite temperatures inaccurate. In this work we formulate a general functional renormalization group approach based on Majorana fermions to overcome these difficulties. We, particularly, implement spin operators via an SO(3) symmetric Majorana representation which does not introduce any unphysical states and, hence, remains applicable to quantum spin models at finite temperatures. We apply this scheme, dubbed pseudo-Majorana functional renormalization group (PMFRG) method, to frustrated Heisenberg models on small spin clusters as well as square and triangular lattices. Computing the finite-temperature behavior of spin correlations and thermodynamic quantities such as free energy and heat capacity, we find good agreement with exact diagonalization and the high-temperature series expansion down to moderate temperatures. We observe a significantly enhanced accuracy of the PMFRG compared to the PFFRG at finite temperatures. More generally, we conclude that the development of functional renormalization group approaches with Majorana fermions considerably extends the scope of applicability of such methods.