Paleoheleomyza – wymarły rodzaj muchówek z rodziny błotniszkowatych i podrodziny Heleomyzinae. Obejmuje tylko jeden opisany gatunek, Paleoheleomyza kotejai. Żył w eocenie na terenie współczesnej Europy.
Taksonomia Rodzaj i gatunek typowy opisane zostały po raz pierwszy w 2005 roku przez Andrzeja Józefa Woźnicę i Andrzeja Palaczyka na łamach „Polskiego Pisma Entomologicznego”. Opisu dokonano na podstawie pojedynczej inkluzji w bursztynie bałtyckim, pochodzącej z epoki eocenu. Nadana nazwa rodzajowa oznacza „pradawna Heleomyza”, zaś epitet gatunkowy nadano na cześć Jana Koteji, polskiego kokcydologa.
Morfologia Muchówka o ciele długości około 2,7 mm.
Głowa jej miała okrągławe oczy złożone, małe i niewystające policzki, jedną parę wibrysów, dobrze wykształcone szczecinki perystomalne, drobno oszczecinione czoło, kwadratowatą płytkę czołową z dwoma równych rozmiarów, nieco dozewnętrznie skierowanymi szczecinkami orbitalnymi, parę dużych szczecinek przyoczkowych w trójkącie przyoczkowym, dobrze wykształcone szczecinki ciemieniowe, skrzyżowane szczecinki pozaprzyoczkowe oraz czułki o trzonku zaopatrzonym w szczecinkę skapularną, nóżce z pojedynczą, dużą szczecinką przednio-grzbietową, pierwszym członie biczyka dużym i okrągłym, a ariście krótszej od wysokości głowy i owłosionej.