We prove that a class of solutions to Einstein’s equations—originally discovered by G. C. McVittie in 1933—includes regular black holes embedded in Friedman-Robertson-Walker cosmologies. If the cosmology is dominated at late times by a positive cosmological constant, the metric is regular everywhere on and outside the black hole horizon and away from the big bang singularity, and the solutions asymptote in the future and near the horizon to the Schwarzschild-de Sitter geometry. For solutions without a positive cosmological constant the would-be horizon is a weak null singularity.