When an ice crystal is born from liquid water, two key changes occur: (i) The molecules order and (ii) the mobility of the molecules drops as they adopt their lattice positions. Most research on ice nucleation (and crystallization in general) has focused on understanding the former with less attention paid to the latter. However, supercooled water exhibits fascinating and complex dynamical behavior, most notably dynamical heterogeneity (DH), a phenomenon where spatially separated domains of relatively mobile and immobile particles coexist. Strikingly, the microscopic connection between the DH of water and the nucleation of ice has yet to be unraveled directly at the molecular level. Here we tackle this issue via computer simulations which reveal that (i) ice nucleation occurs in low-mobility regions of the liquid, (ii) there is a dynamical incubation period in which the mobility of the molecules drops before any ice-like ordering, and (iii) ice-like clusters cause arrested dynamics in surrounding water molecules. With this we establish a clear connection between dynamics and nucleation. We anticipate that our findings will pave the way for the examination of the role of dynamical heterogeneities in heterogeneous and solution-based nucleation.