The first discovered protocetid, Protocetus atavus was described by Fraas 1904 based on a cranium and a number of associated vertebrae and ribs found in middle Lutetian Tethyan marine limestone from Gebel Mokattam near Cairo, Egypt.
Protocetus had a streamlined, whale-like body around 2.5 metres (8.2 ft) long, but was relatively primitive in many respects; it still had small hind flippers, and its front flippers had webbed toes. Its jaws were long and lined with deadly teeth. The shape of the bones in the tails suggests that it may have evolved tail flukes, like those of modern whales, and, while it did not have a true blowhole, the nostrils had already begun to move backwards on the head.
Unlike its more primitive predecessor Pakicetus, the structure of the ears suggests that Protocetus was able to hear properly underwater, although it is unlikely that it could echolocate. Similarly, it retained sufficient olfactory apparatus to have a good sense of smell, although it probably relied more on its eyesight to find prey.