Background: Little is known about the association between the initiation of hepatitis B vaccine (HB vaccine) at birth and completion of the HB vaccine and the national immunization program vaccine (NIPV) series in Fujian, China. Methods: A provincial survey, including children in the community and newborns in hospital, was conducted to evaluate coverage with a timely first dose of HB vaccine and the completion of three doses of HB vaccine and the NIPV series in 2013. A proportion of the samples was rechecked to investigate the relationship between the administration of a timely first dose of HB vaccine and completion of the HB vaccine series and the NIPV series (three doses of HB vaccine, one dose of Bacillus Calmette–Guérin vaccine, three doses of oral poliomyelitis vaccine, three doses of diphtheria–tetanus–pertussis vaccine, one dose of measles-containing vaccine, one dose of Japanese encephalitis attenuated live vaccine, and two doses of group A meningococcal polysaccharide vaccine). Results: A total of 6589 subjects (including 3785 community children and 2804 hospital newborns) were included in this study; 97.34% of them received a timely first dose of HB vaccine (≤24 h after birth) and 99.10% and 88.27% completed the HB vaccine series and the NIPV series, respectively. Among the 1680 children from eight counties who were rechecked, those with a timely first dose of HB vaccine had higher completion rates of the HB vaccine series and the NIPV series than those with a delayed first dose of HB vaccine (99.69% and 88.90% vs. 83.05% and 79.66%, respectively; both p < 0.001). Compared to those with a delayed HB vaccine first dose, the odds ratios for completing the HB vaccine series and the NIPV series among children who received a timely first dose of HB vaccine were 65.96 (95% confidence interval (CI) 21.73–200.25) and 3.24 (95% CI 1.81–5.81), respectively. Conclusions: Coverage with a timely first dose of HB vaccine is high in children in the community and newborns in hospital, and timely receipt of the first dose of HB vaccine is associated with an increased likelihood of completing the HB vaccine series and the NIPV series in Fujian, China.