The paper describes a laboratory investigation of an ultrasonic method which has the potential to become, through further research, a valuable tool for the nondestructive quality control of concrete during construction. The primary objective of the work is to characterize the development of internal structure of the portland cement paste portion of concrete from very early ages on by making use of the behavior of propagated ultrasonic pulses. To do that, however, a suitable ultrasonic method first had to be developed since quite a few publications reported difficulties with such measurements in fresh pastes due to high attenuation. Velocity and attenuation of longitudinal ultrasonic pulses were measured at regular intervals in fresh concretes. The first measurements were usually performed 10 minutes after mixing and continued up to the age of 28 days. Three concretes of different compositions were tested. This paper concentrates on measurements at very early ages. The instrumentation, test set up, and testing procedure are described. The velocity and attenuation results, as well as their interpretation, are then presented. For instance, it is shown that the time of initial set is close to a minimum on the pulse velocity versus age relationship, as well as a maximum on the attenuation versus age relationship.