The interplay between magic number stabilities and superfluidity of small parahydrogen clusters with sizes N=5 to 40 and temperatures 0.5 K</=T</=4.5 K is explored with classical and quantum path integral Monte Carlo calculations. Clusters with N<26 and T</=1.5 K have large superfluid fractions even at the stable magic numbers 13, 19, and 23. In larger clusters, superfluidity is quenched especially at the magic numbers 26, 29, 32, and 37 while below 1 K, superfluidity is recovered for the pairs (27,28), (30,31), and (35,36). For all clusters superfluidity is localized at the surface and correlates with long exchange cycles involving loosely bound surface molecules.