Context. The Near InfraRed Planet Searcher (NIRPS) joined HARPS on the 3.6-m ESO telescope at La Silla Observatory in April 2023, dedicating part of its Guaranteed Time Observations (GTO) program to the radial velocity follow-up of TESS planet candidates to confirm and characterize transiting planets around M dwarfs. Aims. We present the "Sub-Neptunes" subprogram of the NIRPS-GTO, aimed at investigating the composition and formation of sub-Neptunes orbiting M dwarfs. We report the first results of this program with the characterization of the TOI-756 system, which consists of TOI-756 b, a transiting sub-Neptune candidate detected by TESS, as well as TOI-756 c, an additional non-transiting planet discovered by NIRPS and HARPS. Methods. We analyzed TESS and ground-based photometry, high-resolution imaging, and high-precision radial velocities (RVs) from NIRPS and HARPS to characterize the two newly discovered planets orbiting TOI-756, as well as to derive the fundamental properties of the host star. A dedicated approach was employed for the NIRPS RV extraction to mitigate telluric contamination, particularly when the star's systemic velocity was shown to overlap with the barycentric Earth radial velocity. Results. TOI-756 is a M1V-type star with an effective temperature of Teff ~ 3657 K and a super-solar metallicity ([Fe/H]) of 0.20±0.03 dex. TOI-756 b is a 1.24-day period sub-Neptune with a radius of 2.81 ± 0.10 R⊕ and a mass of 9.8‑1.6+1.8 M⊕. TOI-756 c is a cold eccentric (ec = 0.45 ± 0.01) giant planet orbiting with a period of 149.6 days around its star with a minimum mass of 4.05 ± 0.11 MJup. Additionally, a linear trend of 146 m s‑1 yr‑1 is visible in the radial velocities, hinting at a third component, possibly in the planetary or brown dwarf regime. Conclusions. We present the discovery and characterization of the transiting sub-Neptune TOI-756 b and the non-transiting eccentric cold giant TOI-756 c. This system is unique in the exoplanet landscape, standing as the first confirmed example of such a planetary architecture around an M dwarf. With a density of 2.42 ± 0.49 g cm‑3, the inner planet, TOI-756 b, is a volatile-rich sub-Neptune. Assuming a pure H/He envelope, we inferred an atmospheric mass fraction of 0.023 and a core mass fraction of 0.27, which is well constrained by stellar refractory abundances derived from NIRPS spectra. It falls within the still poorly explored radius cliff and at the lower boundary of the Neptune desert, making it a prime target for a future atmospheric characterization with JWST to improve our understanding of this population.