The Ne22(p,γ)Na23 reaction takes part in the neon-sodium cycle of hydrogen burning. This cycle affects the synthesis of the elements between Ne20 and Al27 in asymptotic giant branch stars and novae. The Ne22(p,γ)Na23 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 Ne22(p,γ)Na23 resonances at 156.2, 189.5, and 259.7 keV are reported. Their resonance strengths are derived with 2%–7% uncertainty. In addition, upper limits for three other resonances are greatly reduced. Data are taken using a windowless Ne22 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 ultralow background observed deep underground. The new reaction rate is a factor of 20 higher than the recent evaluation at a temperature of 0.1 GK, relevant to nucleosynthesis in asymptotic giant branch stars.