This laboratory study investigated the damage evolution of sandstone specimens under two types of cyclic loading by monitoring and analyzing changes in the elastic moduli and the ultrasonic velocities during loading. During low-level cyclic loading, the stiffness degradation method was unable to describe the damage accumulations but the ultrasonic velocity measurements clearly reflected the damage development. A crack density parameter is introduced in order to interpret the changes in the tangential modulus and the ultrasonic velocities. The results show the following. (1) Low-level cyclic loading enhanced the anisotropy of the cracks. This results from the compression of intergranular clay minerals and fatigue failure. (2) Irreversible damage accumulations during cyclic loading with an increasing upper stress limit are the consequence of brittle failure in the sandstone’s microstructure.