This paper uses techniques from evolutionary robotics to predict the most energy-efficient upright walking gait for the early human relative Australopithecus afarensis, based on the proportions of the 3.2 million year old AL 288-1 'Lucy' skeleton, and matches predictions against the nearly contemporaneous (3.5-3.6 million year old) Laetoli fossil footprint trails. The technique creates gaits de novo and uses genetic algorithm optimization to search for the most efficient patterns of simulated muscular contraction at a variety of speeds. The model was first verified by predicting gaits for living human subjects, and comparing costs, stride lengths and speeds to experimentally determined values for the same subjects. Subsequent simulations for A. afarensis yield estimates of the range of walking speeds from 0.6 to 1.3 m s-1 at a cost of 7.0 J kg-1 m-1 for the lowest speeds, falling to 5.8 J kg-1 m-1 at 1.0 m s-1, and rising to 6.2 J kg-1 m-1 at the maximum speed achieved. Speeds previously estimated for the makers of the Laetoli footprint trails (0.56 or 0.64 m s-1 for Trail 1, 0.72 or 0.75 m s-1 for Trail 2/3) may have been underestimated, substantially so for Trail 2/3, with true values in excess of 0.7 and 1.0 m s-1, respectively. The predictions conflict with suggestions that A. afarensis used a 'shuffling' gait, indicating rather that the species was a fully competent biped.