Outflows are a key element in the baryon cycle of galaxies, impacting their evolution by extracting gas, momentum, and energy and then injecting them into the surrounding medium. The properties of gas outflows provide a fundamental test for our models of how galaxies transition from a phase of active star formation to quiescence. Here we report the detection of outflowing gas signatures in two recently quenched, massive (M-star similar to 10(10.2) M-circle dot) galaxies at z = 4.106 (NS_274) and z = 7.276 (RUBIES-UDS-QG-z7) observed at rest-frame ultraviolet to near-infrared wavelengths with JWST/NIRSpec. The outflows are traced by blueshifted magnesium (MgII) absorption lines, and in the case of the z = 4.1 system, also by iron (FeII) and sodium (NaI) features. Together, these transitions broadly trace the chemically enriched neutral phase of the gaseous medium. The rest-frame optical spectra of the two sources are similar to those of local post-starburst galaxies, showing deep Balmer stellar features, a relatively low D(n)4000 index, and minimal ongoing star formation on 10 Myr timescales, as traced by the lack of bright nebular and recombination emission lines. This also suggests the absence of strong and radiatively efficient active galactic nucleus activity. The galaxies' star formation histories are consistent with a recent and abrupt quenching, prior to which the average star formation rate was similar to 15 M-circle dot yr(-1) over the last 100 Myr of their lives. In the case of NS_274, dedicated millimeter observations allowed us to also strongly constrain the dust obscured star formation rate to 10 for the z = 4.1 and z = 7.3 systems, respectively, and a similarly pronounced difference in the energy carried by the outflows. Supernova feedback could account for the mass and energy of the outflow in NS_274. However, the low mass loading factor and average gas velocity (similar to 180 km s(-1), which is lower than the stellar velocity dispersion) suggest that the observed outflow is likely not the primary factor behind the quenching of NS_274, but it might represent a relic of the star formation process winding down. Star-formation-related processes seem to also be insufficient to explain the extreme mass outflow rate of RUBIES-UDS-QG-z7, which would require an additional ejective mechanism such as an undetected active galactic nucleus. Finally, the average outflow velocities per unit stellar mass, star formation rate, and surface density of star formation rate are consistent with those of lower-redshift post-starburst galaxies, suggesting that outflows in rapidly quenched galaxies might occur similarly across cosmic time. Our findings hint at the existence of a rich tapestry of galaxy quenching pathways at high redshifts, and they highlight the importance