Background: Because long-term effectiveness of pollen allergen immune therapy (AIT) for allergic rhinitis (AR) is not well-described, we studied effectiveness over 18 years in Denmark. Methods: A register-based cohort study using data on filled prescriptions, 1995–2016, Denmark. In a cohort of 1.1 million intranasal corticosteroid inhaler users (proxy for AR), we matched users treated with grass, birch or mugwort AIT 1:2 with non-treated users on baseline year and 24 characteristics in the 3 years prior to baseline. The primary outcome was the odds ratio (OR) of using anti-allergic nasal inhaler during the pollen season in the treated versus non-treated group by years since baseline. Results: Among 7760 AR patients treated with pollen AIT, the OR of using nasal inhaler 0–5 years after baseline was reduced when compared with 15,520 non-treated AR individuals (0–2 years, OR 0.84 (0.81–0.88); 3–5 years, OR 0.88 (0.84–0.92)), but was close to unity or higher thereafter (6–9 years, OR 1.03 (0.97–1.08); 10–18 years, OR 1.18 (1.11–1.26)). In post hoc analyses, results were more consistent for those who already had 3 of 3 baseline years of use, and in patients using nasal inhaler in the latest pollen season (0–2 years, OR 0.76 (0.72–0.79); 3–5 years OR 0.86 (0.81–0.93); 6–9 years, OR 0.94 (0.87–1.02); 10–18 years, OR 0.94 (0.86–1.04)) as opposed to no such use. Conclusions: Patients treated with pollen AIT in routine care to a higher degree stopped using anti-allergic nasal inhaler 0–5 years after starting the standard 3 years of therapy, and not beyond 5 years. Post hoc analyses suggested effectiveness was more consistent among patients with persistent AR.