Laetoli is a well-known palaeontological locality in northern Tanzania whose outstanding record includes the earliest hominin footprints in the world (3.66 million years old), discovered in 1978 at Site G and attributed to Australopithecus afarensis. Here, we report hominin tracks unearthed in the new Site S at Laetoli and referred to two bipedal individuals (S1 and S2) moving on the same palaeosurface and in the same direction as the three hominins documented at Site G. The stature estimates for S1 greatly exceed those previously reconstructed for Au. afarensis from both skeletal material and footprint data. In combination with a comparative reappraisal of the Site G footprints, the evidence collected here embodies very important additions to the Pliocene record of hominin behaviour and morphology. Our results are consistent with considerable body size variation and, probably, degree of sexual dimorphism within a single species of bipedal hominins as early as 3.66 million years ago. DOI: http://dx.doi.org/10.7554/eLife.19568.001, eLife digest Fossil footprints are extremely useful tools in the palaeontological record. Their physical features can help to identify their makers, but can also be used to infer biological information. How did the track-maker move? How large was it? How fast was it going? Footprints of hominins (namely the group to which humans and our ancestors belong) are pretty rare. Nearly all of the hominin footprints discovered so far are attributed to species of the genus Homo, to which modern humans belong. The only exceptions are the footprints that were discovered in the 1970s at Laetoli (in Tanzania) on a cemented ash layer produced by a volcanic eruption. These are thought to have been made by three members of the hominin species Australopithecus afarensis – the same species as the famous “Lucy” from Ethiopia – around 3.66 million years ago. The extent to which body shape and size varied between different members of Au. afarensis – for example, between males and females – has been the subject of a long debate among researchers. Based on the skeletal remains found so far in East Africa, some scholars believe that individuals only varied moderately, as in modern humans, while others state that it was pronounced, as in some modern apes like gorillas. Masao et al. have now unearthed new bipedal footprints from two individuals who were moving on the same surface and in the same direction as the three individuals who made the footprints documented in the 1970s. The estimated height of one of the new individuals (about 1.65 metres) greatly exceeds those previously published for Au. afarensis. This evidence supports the theory that body size varied considerably amongst individuals within the species. Masao et al. tentatively suggest that the new footprints can be considered as a whole with the 1970s ones. The tall individual may have been the dominant male of a larger group, the others smaller females and juveniles. Thus, considerable differences may have existed between males and females in these remote human ancestors, similar to modern gorillas. The newly discovered tracks are only 150 metres away from the previously discovered sets of footprints. This leaves open the possibility that additional tracks may be unearthed nearby that will further our knowledge about the variability and behaviour of our extinct ancestors. DOI: http://dx.doi.org/10.7554/eLife.19568.002