Recent time-lapse seismic observations in carbonate reservoirs subject to steam-assisted enhanced oil recovery display substantial changes in seismic reflectivity due to the combined effects of saturation, pressure, and temperature. Understanding these field seismic observations requires knowledge of the effects on the seismic wave speeds in bitumen-saturated carbonates. We have conducted ultrasonic measurements of P- and S-wave velocities in bitumen-saturated dolomite taken from the Grosmont Formation in northern Alberta. Wave speeds are measured under a variety of conditions of constant pore pressure, constant effective pressure, and with varying temperature to map the various controlling factors. The temperature-dependent declines of 12% and 9% for the P- and S-wave speeds, respectively, with temperatures from 10°C to 102°C are most notable. Unlike oil sands, at times, the dolomite retains its structure upon removal of the bitumen allowing for measurement of the dry and water-saturated frame properties and their subsequent use in substitutional modeling. None of the standard bounding, inclusion, or Biot-Gassmann family models adequately describe the observations in the heated sample. The deviations may be in part due to the inability of these models to properly incorporate the complex bitumen non-Newtonian rheology including a bulk viscosity.