A trypanosomatid (Trypanosomatidae: Kinetoplastida) associated with a blood-filled female sand fly in Cretaceous Burmese amber, is described in the new genus and species, Paleoleishmania proterus. The genus Paleoleishmania is established as a collective genus for digenetic fossil trypanosomes associated with sand flies. Amastigotes, promastigotes and paramastigotes are described. Paleoleishmania proterus is the first fossil kinetoplastid and provides a minimum age for the digenetic Trypanosomatidae. Its discovery indicates that vector-borne pathogens had been established by the Early Cretaceous.