Background: The number of homeless families has increased considerably since the 1990s in France. We aimed to estimate the homeless children vaccination coverage (VC) for diphtheria, tetanus, polio, measles-mumps-rubella and hepatitis B and identify factors associated with insufficient VC according to birthplace. Methods: A cross-sectional survey was conducted among homeless shelter families in the greater Paris area. A nurse conducted face-to-face interviews and collected vaccination records. We analyzed factors associated with insufficient VC, stratified by birthplace and vaccine, using robust Poisson regression. Results: The study included 214 children born in France and 236 born outside France. VC in French-born homeless children was high (>90% at 24 months for most vaccinations) and similar to levels observed in the general population, whereas VC in those born outside France was low (<50% at 24 months for all vaccines). Factors significantly associated with insufficient VC among children born outside France were age, parents with French-language difficulties, and changing residence at least twice in the previous year. Children in contact with the healthcare system at least once in the previous year had significantly higher VC, irrespective of vaccine and birthplace. Conclusion: Special attention should be paid to homeless children born outside France, with recent European and French recommendations confirming the need for catch-up vaccination in children with undocumented VC.