We present the result from teleseismic travel time inversions for P and S wave data mainly recorded at portable broadband stations in SE Brazil. The stations were deployed at 45 sites within an area 1000 ¿ 1700 km during the years 1992--1999. More than 10,000 relative P and S wave arrival times, including core phases, were obtained from the waveforms using a new coherence functional. These P and S relative phase times are independently inverted for slowness perturbations, earthquake relocations, and station corrections. The final models represent the least amount of structure required to explain the residuals within a defined standard error. The robust and consistent features in the velocity anomaly models are interpreted and their resolution is tested with synthetic case inversions. We confirm the existence of a cylindrical low-velocity anomaly beneath the Paran¿ basin, which has been interpreted by VanDecar et al. <1995> as the fossil conduit through which the initial Tristan da Cunha plume head traveled to generate the Paran¿--Etendeka flood basalts about 130 Ma. We now show that this low-velocity cylindrical structure seems to be confined to the upper mantle. Beneath the upper mantle, the velocity anomalies show a N-S oriented pattern, which we interpret as due to the Nazca plate subducted slab. At lithospheric depths, the Archean, southern part of the S¿o Francisco craton, shows high velocities down to 200--300 km. All areas with Late Cretaceous postrift alkaline intrusions are characterized by low velocities at lithospheric depths.