Understanding nucleation dynamics is important both fundamentally and technologically in materials science and other scientific fields. Two-dimensional (2D) nucleation is the predominant growth mechanism in colloidal crystallization, in which the particle interaction is attractive, and has recently been regarded as a promising method to fabricate varieties of complex nanostructures possessing innovative functionality. Here, polymers are added to a colloidal suspension to generate a depletion attractive force, and the detailed 2D nucleation process on the terrace of the colloidal crystals is investigated. In the system, we first measured the nucleation rate at various area fractions of particles on the terrace, ϕarea. In situ observations at single-particle resolution revealed that nucleation behavior follows the framework of classical nucleation theory (CNT), such as single-step nucleation pathway and existence of critical size. Characteristic nucleation behavior is observed in that the nucleation and growth stage are clearly differentiated. When many nuclei form in a small area of the terrace, a high density of kink sites of once formed islands makes growth more likely to occur than further nucleation because nucleation has a higher energy barrier than growth. The steady-state homogeneous 2D nucleation rate, J, and the critical size of nuclei, r*, are measured by in situ observations based on the CNT, which enable us to obtain the step free energy, γ, which is an important parameter for characterizing the nucleation process. The γ value is found to change according to the strength of attraction, which is tuned by the concentration of the polymer as a depletant.