Sea cows (manatees, dugongs) are the only living marine mammals to feed solely on aquatic plants. Unlike whales or dolphins (Cetacea), the earliest evolutionary history of sirenians is poorly documented, and limited to a few fossils including skulls and skeletons of two genera composing the stem family of Prorastomidae (Prorastomus and Pezosiren). Surprisingly, these fossils come from the Eocene of Jamaica, while stem Hyracoidea and Proboscidea--the putative sister-groups to Sirenia--are recorded in Africa as early as the Late Paleocene. So far, the historical biogeography of early Sirenia has remained obscure given this paradox between phylogeny and fossil record. Here we use X-ray microtomography to investigate a newly discovered sirenian petrosal from the Eocene of Tunisia. This fossil represents the oldest occurrence of sirenians in Africa. The morphology of this petrosal is more primitive than the Jamaican prorastomids' one, which emphasizes the basal position of this new African taxon within the Sirenia clade. This discovery testifies to the great antiquity of Sirenia in Africa, and therefore supports their African origin. While isotopic analyses previously suggested sirenians had adapted directly to the marine environment, new paleoenvironmental evidence suggests that basal-most sea cows were likely restricted to fresh waters.