The entry point and timing of ancient human migration into continental Sahul (the combined landmass of Australia, New Guinea, and Tasmania) are subject to debate. Unique strains of hepatitis B virus (HBV) are endemic among modern-day Australian Aboriginals (HBV/C4) and Indigenous Melanesians (HBV/C3). We postulated that HBV genomes could be used to infer human population movements because the main HBV transmission route in endemic populations is via mother-to-child for genotypes B and C infections. Phylogenetic and phylogeographic analyses of HBV genomes inferred the origin of HBV/C4 to be >59 thousand years ago (ka) (95% HPD: 34-85 ka), and most likely to have occurred on the Sunda Shelf (southeast extension of the continental shelf of Southeast Asia). Our analysis further suggested an age of >51 ka (95% Highest Posterior Density (HPD): 36-67 ka) for the most recent common ancestor of HBV/C4 in Australia, correlating with the arrival time of anatomically modern humans into Australia, with the entry point suggested along a southern route via Timor. While we also inferred the origin of HBC/C3 to be on the Sunda Shelf, our analyses suggested that it was carried into Melanesia by Indigenous Melanesians who migrated through New Guinea north of the highlands. These findings reveal that HBV genomes can be used to infer ancient human population movements.