Since the stress-strain curve of a concrete is not linear, at least under the first loading, one would expect that the presence of stresses would reduce the velocity of ultrasonic pulses in the concrete. The experimental investigation of this expectation is the topic of this paper. Mature concrete cylinders of different compositions were subjected to various types of compression loading (gradually increasing load, repeated loading, etc.), and pulse velocities were measured in various manners (with different frequencies and various paths) both in the loaded and unloaded states. The experimental results clearly indicate that the pulse velocity in concrete is independent of the stress level to a surprisingly large extent, that is, up to about 70% of the compressive strength. This means, in practical terms, that stresses prevailing in the concrete of a structure do not have to be taken into account when pulse velocity data are used for the evaluation of the quality of concrete.