Nucleation plays a critical role in many physical and biological phenomena ranging from crystallization, melting and evaporation to the formation of clouds and the initiation of neurodegenerative diseases. However, nucleation is a challenging process to study in experiments especially in the early stage when several atoms/molecules start to form a new phase from its parent phase. Here, we advance atomic electron tomography to study early stage nucleation at 4D atomic resolution. Using FePt nanoparticles as a model system, we reveal that early stage nuclei are irregularly shaped, each has a core of one to 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 differ from classical nucleation theory (CNT) and to explain them we propose the order parameter gradient (OPG) model. We show the OPG model generalizes CNT and energetically favours diffuse interfaces for small nuclei and sharp interfaces for large nuclei. We further corroborate this model using molecular dynamics simulations of heterogeneous and homogeneous nucleation in liquid-solid phase transitions of Pt. We anticipate that the OPG model is applicable to different nucleation processes and our experimental method opens the door to study the structure and dynamics of materials with 4D atomic resolution.