In 2001 and 2002, a temporary array of 72 seismic recorders was deployed across northern Tasmania (SE Australia), with the aim of imaging the underlying crust and upper mantle using three-dimensional (3-D) teleseismic tomography. Using a recently developed adaptive stacking technique, 6520 relative P wave arrival time residuals have been picked from 101 distant earthquake records spanning a 5 month period. A novel iterative nonlinear tomographic procedure based on a subspace inversion scheme and the fast marching method, a grid-based eikonal solver, is used to map the residual patterns as P wave velocity anomalies. The new scheme proves to be both fast and robust, making it well suited to large data sets and the reconstruction of complex anomalies. The resultant tomographic images of Tasmania exhibit significant lateral perturbations in P wave velocity structure (≤5%) from a 1-D reference model. A marked transition from higher velocities in the east to lower velocities in the west strongly supports the idea that eastern Tasmania is underlain by dense rocks with an oceanic crustal affinity, contrasting with the continentally derived siliciclastic core of western Tasmania. Significantly, the Tamar Fracture System does not overlie the narrow transition from relatively fast to slow velocities, which suggests that it may be a near-surface feature rather than a manifestation of deeper crustal-scale suturing as previously thought. Farther west, an easterly dipping zone of relatively high velocity material beneath the Rocky Cape Group and Arthur Lineament may be related to remnant subduction of oceanic lithosphere associated with the mid-Cambrian Delamerian Orogeny.