Nb3Sn offers significant potential to exceed the performance of niobium for superconducting radio frequency accelerator cavities. The most promising path toward deployment is by tin vapor diffusion coating of Nb cavity interiors via a two step nucleation-then-growth sequence. Reported here is a materials science study of the nucleation process. We manipulated the accessible range of process variables and determined the effect on composition and microstructure using an array of materials characterization tools. Broadly, nucleation deposits tin as a thin surface phase and, under some conditions, as near-micron sized particles as well, resembling Stranski-Krastanov growth. Conditions that impair nucleation promote the formation of defects, such as patches, in subsequent coating growth. Otherwise no significant effect on the subsequently grown coating was found for structures produced during nucleation.