A solid-solid phase transition of colloidal hard spheres confined between two planar hard walls is studied using a combination of molecular dynamics and Monte Carlo simulation. The transition from a solid consisting of five crystalline layers with square symmetry (5□) to a solid consisting of four layers with triangular symmetry (4) is shown to occur through a nonclassical nucleation mechanism that involves the initial formation of a precritical liquid cluster, within which the cluster of the stable 4 phase grows. Free-energy calculations show that the transition occurs in one step, crossing a single free-energy barrier, and that the critical nucleus consists of a small 4 solid cluster wetted by a metastable liquid. In addition, the liquid cluster and the solid cluster are shown to grow at the planar hard walls. We also find that the critical nucleus size increases with supersaturation, which is at odds with classical nucleation theory. The -solid-like cluster is shown to contain both face-centered-cubic and hexagonal-close-packed ordered particles.