An alcohol collection of 990 fleas from Madagascar (2003-2005) was deposited in the Field Museum of Natural History, Chicago, and recently made available for study. Among the material were two new and undescribed taxa. The male and female sex of Paractenopsyllus madagascarensis sp. n. is described and host associations are discussed. In addition, a description of the heretofore unknown female of Paractenopsyllus raxworthyi Duchemin & Ratovonjato, 2004 is provided. The tenrec Microgale drouhardi G. Grandidier, 1934 is also reported as a new host record for P. raxworthyi. Host associations for all known records of species of Paractenopsyllus are presented as a table and a key to the known species of Paractenopsyllus is included.