Characterization of dolomitic limestone rock samples with increasing levels of damage is presented using linear and nonlinear ultrasonic approaches. Limestone test samples with increasing levels of damage were created artificially by exposing virgin samples to increasing temperature levels of 100, 200, 300, 400, 500, 600, and 700oC for a ninety minute period of time. The linear characterization is based upon the concept of complex moduli, which is estimated using ultrasonic dilatational and shear phase velocity measurements and corresponding attenuations. The nonlinear approach is based upon non-collinear wave mixing, involving mixing of two dilatational waves. Criteria were used to assure that the detected scattered wave originated via wave interaction in the limestone and not from nonlinearities in the testing equipment. These criteria included frequency and propagating direction of the resultant scattered wave, and the time-of-flight separation between the two primary waves and the resulting scattered wave. It was observed that both the linear and nonlinear approaches are able to characterize the level of damage in limestone rock.