A variational principle that can serve as the basis for a magneto-elastic stability (or buckling) problem is constructed. For the two cases of soft ferromagnetic media and superconductors, respectively, it is shown how the variational principle directly yields an explicit expression for the buckling value. The formulation starts from a specific choice for a magneto-elastic Lagrangian L (associated with the so-called Maxwell-Minkowski model for magneto-elastic interactions). For the evaluation of the principle the first and second variations of L are calculated both inside and outside the solid magneto-elastic body. Thus, a general buckling criterion, consisting of an expression for the critical field value, together with a set of constraints for the field variables occurring in the right-hand side of this expression, is constructed. Finally, more detailed formulations are given for, successively, soft ferromagnetic bodies and superconductors. Applications to specific structures, yielding explicit numerical values for the magneto-elastic buckling fields, will be given in a forthcoming paper.