During November 2008-July 2009, we investigated the origin of unknown fever in Senegalese patients with a negative malaria test result, focusing on potential rickettsial infection. Using molecular tools, we found evidence for Rickettsia felis-associated illness in the initial days of infection in febrile Senegalese patients without malaria.