Medicine Lake volcano (MLV) in northeastern California is the largest-volume volcano in the Cascade Range. The upper-crustal structure of this Quaternary shield volcano is well known from previous geological and geophysical investigations. In 1981, the U.S. Geological Survey conducted a teleseismic tomography experiment on MLV to explore its deeper structure. The images we present, calculated using a modern form of the ACH-inversion method, reveal that there is presently no hint of a large (> 100 km3), hot magma reservoir in the crust. The compressional-wave velocity perturbations show that directly beneath MLV's caldera there is a zone of increased seismic velocity. The perturbation amplitude is +10% in the upper crust, +5% in the lower crust, and +3% in the lithospheric mantle. This positive seismic velocity anomaly presumably is caused by mostly subsolidus gabbroic intrusive rocks in the crust. Heat and melt removal are suggested as the cause in the upper mantle beneath MLV, inferred from petro-physical modeling. The increased seismic velocity appears to be nearly continuous to 120 km depth and is a hint that the original melts come at least partly from the lower lithospheric mantle. Our second major finding is that the upper mantle southeast of MLV is characterized by relatively slow seismic velocities (-1%) compared to the northwest side. This anomaly is interpreted to result from the elevated temperatures under the northwest Basin and Range Province.