The alloying mechanism of high-capacity tin anodes for sodium-ion batteries is investigated using a combined theoretical and experimental approach. Ab initio random structure searching (AIRSS) and high-throughput screening using a species-swap method provide insights into a range of possible sodium-tin structures. These structures are linked to experiments using both average and local structure probes in the form of operando pair distribution function analysis, X-ray diffraction, and 23Na solid-state nuclear magnetic resonance (ssNMR), and ex situ 119Sn ssNMR. Through this approach, we propose structures for the previously unidentified crystalline and amorphous intermediates. The first electrochemical process of sodium insertion into tin results in the conversion of crystalline tin into a layered structure consisting of mixed Na/Sn occupancy sites intercalated between planar hexagonal layers of Sn atoms (approximate stoichiometry NaSn3). Following this, NaSn2, which is predicted to be thermodynamically stable by AIRSS, forms; this contains hexagonal layers closely related to NaSn3, but has no tin atoms between the layers. NaSn2 is broken down into an amorphous phase of approximate composition Na1.2Sn. Reverse Monte Carlo refinements of an ab initio molecular dynamics model of this phase show that the predominant tin connectivity is chains. Further reaction with sodium results in the formation of structures containing Sn-Sn dumbbells, which interconvert through a solid-solution mechanism. These structures are based upon Na5-xSn2, with increasing occupancy of one of its sodium sites commensurate with the amount of sodium added. ssNMR results indicate that the final product, Na15Sn4, can store additional sodium atoms as an off-stoichiometry compound (Na15+xSn4) in a manner similar to Li15Si4.