Two sets of prints were left by Homo ergaster, an early ancestor of modern humans, in separate rock layers near Ileret in northern Kenya.
Laser scanning revealed that the creature walked the same way as people do today.
The green prints on the optical laser scan indicate a modern stride
The prints bore all the hallmarks of a modern human stride, including an arched foot, short toes, and a big toe that was parallel to the others.
As in modern humans, weight was transferred from the heel to the ball of the foot and then to the big toe with each step.
The find is the first of its kind since the famous discovery 30 years ago of footprints dating back 3.75million years at Laetoli, Tanzania.
These older prints are thought to have been left by the more primitive and ape-like Australopithecus.
Although this creature also appears to have walked upright, it had a shallow arch and a splayed big toe characteristic of apes.
The Ileret prints, pressed into solidified layers of ancient mud, consisted of an upper and lower set five metres apart, one isolated smaller print may have been left by a child.
The scientists estimated the adults were about 5ft 9" from their stride length.
Scientists led by Dr Matthew Bennett, from the University of Bournemouth in Poole, scanned the prints and compared them with those of modern humans and the Laetoli prints.
They wrote in the journal Science: 'The Ileret prints show that by 1.5 million years, hominins had evolved an essentially modern human foot function and style of bipedal locomotion.'
Our species, Homo sapiens, first appeared 200,000 years ago.