We report an experimental study of the emergence of nontrivial topological winding and long-range order across the paramagnetic-to-skyrmion lattice transition in the transition metal helimagnet MnSi. Combining measurements of the susceptibility with small-angle neutron scattering, neutron-resonance spin-echo spectroscopy, and all-electrical microwave spectroscopy, we find evidence of skyrmion textures in the paramagnetic state exceeding 10(3) angstrom, with lifetimes above several 10(-9) s. Our experimental findings establish that the paramagnetic-to-skyrmion lattice transition in MnSi is well described by the Landau soft-mode mechanism of weak crystallization, originally proposed in the context of the liquid-to-crystal transition. As a key aspect of this theoretical model, the modulation vectors of periodic small-amplitude components of the magnetization form triangles that add to zero. In excellent agreement with our experimental findings, these triangles of the modulation vectors entail the presence of the nontrivial topological winding of skyrmions already in the paramagnetic state of MnSi when approaching the skyrmion lattice transition.