The fossil of the amphibious Phiomicetus anubis was originally discovered in Egypt's Western Desert.
Its skull resembles that of Anubis, the ancient Egyptian jackal-headed god of the dead after which it was named.
The ancestors of modern whales developed from deer-like mammals that lived on land over the course of 10 million years.
Weighing an estimated 600kg and three metres (10ft) in length, the Phiomicetus anubis had strong jaws to catch prey, according to the study published by the Proceedings of the Royal Society B on Wednesday. The whale was able to walk on land and swim in water.
The partial skeleton was found in Egypt's Fayum Depression and analysed by scientists at Mansoura University. Although the area is now desert, it was once covered by sea and is a rich source of fossils.
"Phiomicetus anubis is a key new whale species, and a critical discovery for Egyptian and African palaeontology," the study's lead author, Abdullah Gohar, told Reuters news agency.
While this is not the first time the fossil of a whale with legs has been found, the Phiomicetus anubis is believed to be the earliest type of semi-aquatic whale to be discovered in Africa.
The first whales are thought to have first evolved in South Asia around 50 million years ago. In 2011, a team of palaeontologists in Peru discovered a 43-million-year-old whale fossil with four legs, webbed feet and hooves.