Over the last decade, a variational principle based on a generalisation of Taylor's relaxation, referred to as multi-region relaxed magnetohydrodynamics (MRxMHDs) has been developed. The numerical solutions of the MRxMHD equilibria have been constructed using the Stepped Pressure Equilibrium Code (SPEC) (Hudson et al 2012 Phys. Plasmas 19 112502). In principle, SPEC could also be established to describe the MRxMHD stability of an equilibrium. In this work, a theoretical framework is developed to relate the second variation of the energy functional to the so-called Hessian matrix, enabling the prediction of MHD linear instabilities of cylindrical plasmas, and is implemented in SPEC. The negative and positive eigenvalues of the Hessian matrix predict the stability of an equilibrium. Verification studies of SPEC stability results with the M3D-C1 code and the tearing mode $\Delta^{^{\prime}}$ criterion have been conducted for ideal and resistive MHD instabilities, respectively, in a pressureless cylindrical tokamak, and have shown good agreement. Our stability analysis is a critical step towards understanding the MHD stability of three-dimensional MHDs where nested flux surfaces, magnetic islands and stochastic regions co-exist.