The earliest known fossil bats are at least 50 million years old. They were widespread across the New and Old Worlds, already possessing fully developed wings and echolocating abilities. These facts suggest that the origin of bats substantially predates the earliest known fossil bats. In this paper we describe a new fossil bat discovered from 46 million year old sediments in Africa. This specimen represents the earliest known placental mammal from sub-Saharan Africa. The new bat has structures of the middle ear indicating that it had a highly developed form of echolocation. Modern bats with similar structures use a very sophisticated form of echolocation that allows them to forage for insects in dense forest undergrowth. The presence of sophisticated echolocating abilities in a 46 million year old bat indicates that bats had reached modern levels of behavioral and morphological diversity by this time.