The Bering Land Bridge (BLB) last connected Eurasia and North America during the Pleistocene. Although the BLB would have enabled transfers of terrestrial biota in both directions, it also acted as an ecological filter whose permeability varied considerably over time. Here we explore the possible impacts of this ecological corridor on genetic diversity within, and connectivity among, populations of a once wide-ranging group, the caballine horses (Equus spp.). Using a panel of 187 mitochondrial and eight nuclear genomes recovered from present-day and extinct caballine horses sampled across the Holarctic, we found that Eurasian horse populations initially diverged from those in North America, their ancestral continent, around 1.0-0.8 million years ago. Subsequent to this split our mitochondrial DNA analysis identified two bi-directional long-range dispersals across the BLB ~875-625 and ~200-50 thousand years ago, during the Middle and Late Pleistocene. Whole genome analysis indicated low levels of gene flow between North American and Eurasian horse populations, which likely occurred as a result of these inferred dispersals. Nonetheless, mitochondrial and nuclear diversity of caballine horse populations retained strong phylogeographic structuring. Our results suggest that barriers to gene flow, currently unidentified but possibly related to habitat distribution across Beringia or ongoing evolutionary divergence, played an important role in shaping the early genetic history of caballine horses, including the ancestors of living horses within Equus ferus.