We use classical density functional theory (cDFT) to calculate fluid-solid surface tensions for fcc and bcc crystals formed by hard spheres and Lennard-Jones (LJ) particles. For hard spheres, our results show that the recently introduced “explicitly stable” functionals perform as well as the state of the art, and for both interaction potentials, our results compare well to simulation. We use the resulting bulk and interfacial energies for LJ to parametrize a capillary model for the free energy of small solid clusters and thereby determine the relative stability of bcc and fcc LJ clusters. We show a crossover from bcc to fcc stability as cluster size increases, thus providing insight into long-standing tension between simulation results and theoretical expectations. We also confirm that the bcc phase in contact with a vapor is unstable, thus extending earlier zero-temperature results. Our Letter demonstrates the potential of cDFT as an important tool in understanding crystallization and polymorphism.