Lead-halide perovskite nanocrystals such as CsPbBr$_3$, exhibit efficient photoluminescence (PL) up-conversion, also referred to as anti-Stokes photoluminescence (ASPL). This is a phenomenon where irradiating nanocrystals up to 100 meV below gap results in higher energy band edge emission. Most surprising is that ASPL efficiencies approach unity and involve single photon interactions with multiple phonons. This is unexpected given the statistically disfavored nature of multiple-phonon absorption. Here, we report and rationalize near-unity anti-Stokes photoluminescence efficiencies in CsPbBr$_3$ nanocrystals and attribute it to resonant multiple-phonon absorption by polarons. The theory explains paradoxically large efficiencies for intrinsically disfavored, multiple-phonon-assisted ASPL in nanocrystals. Moreover, the developed microscopic mechanism has immediate and important implications for applications of ASPL towards condensed phase optical refrigeration.