We determine the phase diagram of a binary mixture of small and large hard spheres with a size ratio of 0.3 using free-energy calculations in Monte Carlo simulations. We find a stable binary fluid phase, a pure face-centered-cubic (fcc) crystal phase of the small spheres, and binary crystal structures with LS and LS(6) stoichiometries. Surprisingly, we demonstrate theoretically and experimentally the stability of a novel interstitial solid solution in binary hard-sphere mixtures, which is constructed by filling the octahedral holes of an fcc crystal of large spheres with small spheres. We find that the fraction of octahedral holes filled with a small sphere can be completely tuned from 0 to 1. Additionally, we study the hopping of the small spheres between neighboring octahedral holes, and interestingly, we find that the diffusion increases upon increasing the density of small spheres.