The $^{22}$Ne(p,$\gamma$)$^{23}$Na reaction takes part in the neon-sodium cycle of hydrogen burning. This cycle affects the synthesis of the elements between $^{20}$Ne and $^{27}$Al in asymptotic giant branch stars and novae. The $^{22}$Ne(p,$\gamma$)$^{23}$Na reaction rate is very uncertain because of a large number of unobserved resonances lying in the Gamow window. At proton energies below 400\,keV, only upper limits exist in the literature for the resonance strengths. Previous reaction rate evaluations differ by large factors. In the present work, the first direct observations of the $^{22}$Ne(p,$\gamma$)$^{23}$Na resonances at 156.2, 189.5, and 259.7\,keV are reported. Their resonance strengths have been derived with 2-7\% uncertainty. In addition, upper limits for three other resonances have been greatly reduced. Data were taken using a windowless $^{22}$Ne gas target and high-purity germanium detectors at the Laboratory for Underground Nuclear Astrophysics in the Gran Sasso laboratory of the National Institute for Nuclear Physics, Italy, taking advantage of the ultra-low background observed deep underground. The new reaction rate is a factor of 5 higher than the recent evaluation at temperatures relevant to novae and asymptotic giant branch stars nucleosynthesis.