The microstructure of cement-based materials evolves during cement hydration. The foundation of the microstructure is laid during the setting period of concrete. This study experimentally monitors the evolving microstructure network of very early-age cement paste during the setting period. The ultrasonic wave reflection method was applied to probe paste samples, which allows us to obtain the frequency dependence of mechanical impedance. The frequency dependence is due to the development of a pore network and hence inversely describes the initial setting of concrete. A total of 11 cement paste mixes were prepared a different water-to-cement ratios and with the use of various admixtures. Finally, the critical time of frequency-dependent impedance is compared with the initial setting time measured by a Vicat needle test, and the results are discussed with the length of pore path.