The origin of Australopithecus, the genus widely interpreted as ancestral to Homo, is a central problem in human evolutionary studies. Australopithecus species differ markedly from extant African apes and candidate ancestral hominids such as Ardipithecus, Orrorin and Sahelanthropus. The earliest described Australopithecus species is Au. anamensis, the probable chronospecies ancestor of Au. afarensis. Here we describe newly discovered fossils from the Middle Awash study area that extend the known Au. anamensis range into northeastern Ethiopia. The new fossils are from chronometrically controlled stratigraphic sequences and date to about 4.1-4.2 million years ago. They include diagnostic craniodental remains, the largest hominid canine yet recovered, and the earliest Australopithecus femur. These new fossils are sampled from a woodland context. Temporal and anatomical intermediacy between Ar. ramidus and Au. afarensis suggest a relatively rapid shift from Ardipithecus to Australopithecus in this region of Africa, involving either replacement or accelerated phyletic evolution.