Nucleation plays a critical role in many physical and biological phenomena that range from crystallization, melting and evaporation to the formation of clouds and the initiation of neurodegenerative diseases1-3. However, nucleation is a challenging process to study experimentally, especially in its early stages, when several atoms or molecules start to form a new phase from a parent phase. A number of experimental and computational methods have been used to investigate nucleation processes4-17, but experimental determination of the three-dimensional atomic structure and the dynamics of early-stage nuclei has been unachievable. Here we use atomic electron tomography to study early-stage nucleation in four dimensions (that is, including time) at atomic resolution. Using FePt nanoparticles as a model system, we find that early-stage nuclei are irregularly shaped, each has a core of one to a few atoms with the maximum order parameter, and the order parameter gradient points from the core to the boundary of the nucleus. We capture the structure and dynamics of the same nuclei undergoing growth, fluctuation, dissolution, merging and/or division, which are regulated by the order parameter distribution and its gradient. These experimental observations are corroborated by molecular dynamics simulations of heterogeneous and homogeneous nucleation in liquid-solid phase transitions of Pt. Our experimental and molecular dynamics results indicate that a theory beyond classical nucleation theory1,2,18 is needed to describe early-stage nucleation at the atomic scale. We anticipate that the reported approach will open the door to the study of many fundamental problems in materials science, nanoscience, condensed matter physics and chemistry, such as phase transition, atomic diffusion, grain boundary dynamics, interface motion, defect dynamics and surface reconstruction with four-dimensional atomic resolution.