Archaeological data from Wallacea (Indonesia) and elsewhere are summarized to show that the history of seafaring begins in the Early Pleistocene, and that this human capability eventually led to Middle Palaeolithic ocean crossings in the general region of Australia. To understand better the technological magnitude of these many maritime accomplishments, a series of replicative experiments are described, and the theoretical conditions of these experiments are examined. The proposition is advanced that hominid cognitive and cultural evolution during the Middle and early Late Pleistocene have been severely misjudged. The navigational feats of Pleistocene seafarers confirm the cultural evidence of sophistication available from the study of palaeoart.With comments from Mike Morwood, Michael Rowland, Matthew Spriggs, Iain Davidson, Ursula Mania, and G.A. Clark and followed by a reply from the author.