Supersolid, an exotic quantum state of matter that consists of particles forming an incompressible solid structure while simultaneously showing superfluidity of zero viscosity, is one of the long-standing pursuits in fundamental research. Although the initial report of $^4$He supersolid turned out to be an artefact, this intriguing quantum matter has inspired enthusiastic investigations into ultracold quantum gases. Nevertheless, the realization of supersolidity in condensed matter remains elusive. Here we find evidence for a quantum magnetic analogue of supersolid—the spin supersolid—in the recently synthesized triangular-lattice antiferromagnet Na$_2$BaCo(PO$_4$)$_2$. Notably, a giant magnetocaloric effect related to the spin supersolidity is observed in the demagnetization cooling process, manifesting itself as two prominent valley-like regimes, with the lowest temperature attaining below 100 mK. Not only is there an experimentally determined series of critical fields but the demagnetization cooling profile also shows excellent agreement with the theoretical simulations with an easy-axis Heisenberg model. Neutron diffractions also successfully locate the proposed spin supersolid phases by revealing the coexistence of three-sublattice spin solid order and interlayer incommensurability indicative of the spin superfluidity. Thus, our results reveal a strong entropic effect of the spin supersolid phase in a frustrated quantum magnet and open up a viable and promising avenue for applications in sub-kelvin refrigeration, especially in the context of persistent concerns about helium shortages.