We employ a new thermodynamic method for self-consistent computation of compositional and thermal effects on phase transition depths, density, and seismic velocities. Using these profiles, we compare theoretical and observed differential traveltimes between P410s and P (T-410) and between P600s and P410s (T660-410) that are affected only by seismic structure in the upper mantle. The anticorrelation between T-410 and T660-410 suggests that variations in T-410 and T660-410 of similar to 8 s are due to lateral temperature variations in the upper mantle transition zone of similar to 400 K. If the mantle is a mechanical mixture of basaltic and harzburgitic components, our traveltime data suggest that the mantle has an average temperature of 1600 +/- 50 K, in agreement with temperature estimates from magma compositions of mid-ocean ridge basalts. We infer a 100 K hotter mantle if we assume the mantle to have a homogeneous pyrolitic composition. The transition-zone temperature beneath hotspots and within subduction zones is relatively high and low, respectively. However, the largest variability in T-410 and T660-410 is recorded by global stations far from subduction zones and hotspots. This indicates that the 400 K variation in upper mantle temperature is complicated by tilted upwellings, slab flattening and accumulation, ancient subduction, and processes unrelated to present-day subduction and plume ascent.