Seismic velocity models provide important constraints on Greenland’s deep structure, which, in turn, has profound implications for our understanding of the tectonic history of this region. However, the resolution of seismic models has been limited by a sparse network, particularly in northern and central Greenland. We address these limitations by generating new high-resolution Rayleigh-wave phase velocity maps encompassing Greenland and northeastern Canada by processing over three decades of teleseismic earthquake records and incorporating recently added stations in Greenland and Arctic Canada. These phase velocity maps are sensitive to structure from the lower crust down to the sub-lithospheric mantle (25–185 s period). We find significant heterogeneity and a strong correlation between isotropic and anisotropic seismic velocities with inferred geological structure. High seismic velocities associated with cratonic lithosphere are broadly divided into two regions, with a belt of reduced velocity spanning central Greenland, which we interpret as lithospheric erosion resulting from interaction between the Greenland continental keel and the Iceland plume. Within each region, we identify tectonic subdivisions that suggest fundamental differences between the blocks that make up Precambrian Greenland. In the south, the North Atlantic craton (NAC) has a high-velocity keel exhibiting anisotropic stratification. Between the NAC and the cratonic lithosphere further north, the Proterozoic Nagssugtoqidian orogenic belt shows a distinct signature of reduced seismic velocity to 75 s period, but then appears to pinch out at depth. The northern Greenland lithosphere exhibits significant isotropic heterogeneity, with a distinct core of high velocities in the northwest (55–75 s period) giving way to a set of distinct east-west trending high-velocity belts at longer periods. At all periods sensitive to the lithospheric mantle in this region, anisotropic fast orientations are E–W, consistent with a north–south Precambrian assembly of the Greenland shield. In contrast to the NAC, there is no evidence of anisotropic stratification in the northern part of the cratonic keel. Based on both isotropic and anisotropic phase-velocity anomalies, we suggest that the Phanerozoic Caledonian and Ellesmerian-Franklinian fold belts are relatively thin-skinned features onshore Greenland, though the Caledonian belt may have a stronger signature off the east coast. At the longest periods, a prominent low-velocity anomaly initially centred on Iceland migrates northwards and spreads beneath central-eastern Greenland. Coupled with NW–SE trending anisotropy, this feature is interpreted as the effect of mantle flow radiating outward from the Iceland plume and interacting with the eroded Greenland lithosphere.