Parasites are virtually ubiquitous, and this has probably been the case for quite some time. The record of parasitic mites (sensu lato) goes back as far as the Carboniferous (~359–259 mya) and, in fact, they are one of the most reported parasites in amber. The six-legged larvae of the mite group Parasitengona have a wide host range, among which are flies. Here we report for the first time cases of larval erythraeoidean mites, commonly referred to as long-legged velvet mites, parasitising gall midges (Cecidomyiidae) in about 100 million years old (Cretaceous) Kachin amber, Myanmar. In three of the four cases here reported, a single erythraeoidean mite was attached to a gall midge, while in one of the cases two mites are associated to a gall midge host. Of the reported gall midges, one specimen represents the ingroup Lestremiinae, two represent unnamed lineages closely related to Cecidomyiinae, and one specimen might represent the group Cecidomyiinae, being the earliest record of this group so far. In the extant fauna, there are no records of associations of erythraeoidean larvae with gall midges. After the Cretaceous, long-legged velvet mites may have shifted their host range, although knowledge on the host range of parasitengonan mites is still limited to arrive to definitive conclusion.