Universal hepatitis B vaccination of newborns was implemented in Russia starting from 1998. From 1998 to 2019, the incidence of acute hepatitis B reduced from 43.8 to 0.57 cases per 100,000 population. Here, we assessed the timely coverage of newborns with the birth dose (HepB-BD), second dose (HepB-2nd), and three vaccine doses (HepB3) in two remote regions of Russia with low (Belgorod Oblast) and high (Yakutia) levels of hepatitis B virus (HBV) endemicity. Vaccination data were obtained from the medical records of 1000 children in Yakutia and 2182 children in Belgorod Oblast. Sera of healthy volunteers from Belgorod Oblast (n = 1754) and Yakutia (n = 1072) across all age groups were tested for serological markers of HBV to assess the infection prevalence and herd immunity. Average HepB-BD coverage was 99.2% in Yakutia and 89.4% in Belgorod Oblast (p < 0.0001) and in both regions varied significantly, from 66% to 100%, between medical centers. The principal reason for the absence of HepB-BD was parent refusal, which accounted for 63.5% of cases of non-vaccination (83/123). While timely HepB-2nd coverage was only 55.4%–64.7%: HepB3 coverage by the age of one year exceeded 90% in both study regions. HBV surface antigen (HBsAg) prevalence in the 1998–2019 birth cohort was 0.2% (95% CI: 0.01–1.3%) in Belgorod Oblast and 3.2% (95% CI: 1.9–5.2%) in Yakutia. The proportion of persons testing negative for both antibodies to HBsAg (anti-HBs) and antibodies to HBV core antigen (anti-HBc) in the 1998–2019 birth cohort was 26.2% (125/481) in Belgorod Oblast and 32.3% (162/501) in Yakutia. We also assessed the knowledge of and attitude towards vaccination among 782 students and teachers of both medical and non-medical specialties from Belgorod State University. Only 60% of medical students knew that hepatitis B is a vaccine-preventable disease. Both medical and nonmedical students, 37.8% and 31.3%, respectively, expressed concerns about safety and actual necessity of vaccination. These data indicate the need to introduce a vaccine delivery audit system, improve medical education with respect to vaccination strategies and policies, and reinforce public knowledge on the benefits of vaccination.