We introduce QRDM-NEVPT2: a hybrid quantum-classical implementation of strongly-contracted N-electron Valence State $2^{nd}$-order Perturbation Theory (SC-NEVPT2), in which the Complete Active Space Configuration Interaction (CASCI) step, capturing static correlation effects, is replaced by a simulation performed on a quantum computer. Subsequently, n-particle Reduced Density Matrices (n-RDMs) measured on a quantum device are used directly in a classical SC-NEVPT2 calculation, which recovers remaining dynamic electron correlation effects approximately. We also discuss the use of the cumulant expansion to approximate the whole 4-RDM matrix or only its zeros. In addition to noiseless state-vector quantum simulations, we demonstrate, for the first time, a hybrid quantum-classical multi-reference perturbation theory calculation, with the quantum part performed on a quantum computer.