The genus Mickoleitia and family Mickoleitiidae was named in honor of German zoologist Gerhard Mickoleit from the University of Tübingen, who was among the first proponents of Willi Hennig's "Phylogenetic Systematics".

The fossil nymphs of the genus Mickoleitia are not especially rare in the limestones of the Crato Formation; the local brick workers even have a common Brazilian name for them ("Abacaxi" = pineapple).

The German biologist Rainer Willmann described the nymphs in a chapter in Martill, Bechly & Loveridge (2007) and erroneously attributed them to the extinct stem group mayfly family Cretereismatidae that he described based on adult specimens from the same locality.

During the work for this monograph on the Crato Formation the German palaeoentomologist Günter Bechly and entomologist Arnold H. Staniczek discovered in the fossil collection of the Stuttgart State Museum of Natural History the very adult specimen that later would become the holotype of Mickoleitia longimanus.

Most likely the abdomen was provided with three caudal filaments (two lateral cerci and the median epiproct) as in modern mayflies and their Permian stem group representatives (Permoplectoptera, e.g. Protereismatidae).

Since males of modern mayflies and of Permoplectoptera have gonopods on the 9th abdominal segment that are developed as genital claspers to grip the female for copulation, such a character state and behavior is also likely for Coxoplectoptera, who have an intermediate position as phylogenetic link between these two groups.

Many of the fossil nymphs are preserved in a characteristic posture with arched back, erect antennae and terminal filaments, and forelegs always in catching position similar to a praying mantis.

Likewise, the forelegs are developed as slender subchelate raptorial legs with nearly identical segment proportions as in the adult stage, but with a shorter tibia that may have been fused with the single-segmented tarsus, which ended in an unpaired claw.

The abundance of fossils, the circumstances of preservation and special anatomical adaptations (7 pairs of abdominal gills, 3 caudal filaments with dense rows of swimming hairs) prove that the larvae have been living in freshwater of streams and rivers, just like those of modern mayflies.

Before this discovery the paranotal-hypothesis and the leg-exite-hypothesis have been considered as incompatible alternative explanations, which have both been supported by a set of evidences from the fossil record, comparative morphology, developmental biology and genetics.

However, the larvae of Coxoplectoptera show that the abdominal gills of mayflies and their ancestors, which are generally considered as corresponding structures to insect wings, articulated within the dorsal tergite plates.

Staniczek, Bechly & Godunko (2011) therefore suggested a new hypothesis that could reconcile the apparently conflicting evidence from paleontology and developmental genetics: wings originated as stiff outgrowths of tergal plates (paranota), and only later in evolution became mobile, articulated appendages through secondary recruiting of leg genes.

The order Coxoplectoptera contains a single family Mickoleitiidae with two genera from the Mesozoic: Mickoleitia (Early Cretaceous, Crato Formation, Brazil): Mesogenesia (Middle or Late Jurassic, Transbaikals):