(1) Background: In Manitoba, most people get the HPV vaccine through a publicly funded school-based program. If they miss the school-based program, they remain eligible for the free HPV immunization program. This study explored whether invitation and reminder letters would increase HPV vaccine uptake among adult women who remained eligible for the publicly funded program. (2) Methods: Eligible individuals were randomized into three groups of 4650 women each. Intervention groups I and II were mailed an information package inviting them to be vaccinated. Six weeks later, intervention group II received a reminder letter if they remained unvaccinated. The control group received no correspondence related to HPV vaccination. Vaccination status, defined as at least one dose of an approved HPV vaccine, was calculated six months after the packages were mailed. (3) Results: Overall, 4.0% (3.4-4.6%,