Gravitational wave emission by coalescing black holes (BHs) kicks the remnant BH with a typical velocity of hundreds of km/s. This velocity is sufficiently large to remove the remnant BH from a low-mass galaxy but is below the escape velocity from the Milky Way (MW) galaxy. If central BHs were common in the galactic building blocks that merged to make the MW, then numerous BHs that were kicked out of low-mass galaxies should be freely floating in the MW halo today. We use a large statistical sample of possible merger tree histories for the MW to estimate the expected number of recoiled BH remnants present in the MW halo today. We find that hundreds of BHs should remain bound to the MW halo after leaving their parent low-mass galaxies. Each BH carries a compact cluster of old stars that populated the core of its original host galaxy. Using the time-dependent Fokker-Planck equation, we find that present-day clusters are ~< 1 pc in size, and their central bright regions should be unresolved in most existing sky surveys. These compact systems are distinguishable from globular clusters by their internal (Keplerian) velocity dispersion greater than one hundred km/s and their high mass-to-light ratio owing to the central BH. An observational discovery of this relic population of star clusters in the MW halo, would constrain the formation history of the MW and the dynamics of BH mergers in the early Universe. A similar population should exist around other galaxies, and may potentially be detectable in M31 and M33.