The McMurray Formation of the Athabasca Oil Sands is one of the largest hydrocarbon resources on Earth and contains an extensive record of Early Cretaceous sedimentation. The provenance of the sandstones that constitute this formation has remained largely unknown. New U-Pb detrital zircon ages (n = 848) record a complicated and variable provenance history that involves several major tectonic regions from across North America. The McMurray Formation contains detrital-zircon signatures indicating sediment sources associated with the Canadian Shield, eastern North America, and the Canadian Cordillera. Vertical stratigraphic changes in the dominant detrital-zircon signatures in the McMurray Formation indicate that provenance of the sediment varied during deposition of the unit. Lowermost deposits in the formation are characterized by zircons with ages of ca. 1800–1900 Ma and ca. 2600–2800 Ma, interpreted as derived from the Canadian Shield. Most of the sediment in the McMurray Formation contains detrital zircons with U-Pb ages of ca. 300–600 Ma and ca. 1000–1200 Ma, interpreted to have been derived originally from Appalachian and Grenville sources in eastern North America. Uppermost samples in the McMurray Formation contain abundant zircons with ages less than 250 Ma, derived from the North American Cordillera. When and how sediments from eastern North America were transported to the Athabasca Oil Sands region of Canada is unclear. We propose the sediments were transported either directly from eastern North America during the Early Cretaceous or recycled during the Early Cretaceous from sub-Cretaceous sedimentary strata in western Canada or the southwestern United States. The presence of Proterozoic and Paleozoic zircons in the Athabasca Oil Sands highlights the importance of Appalachian-derived sediment in the Lower Cretaceous stratigraphic record of western Canada.