Carmenelectra is known from a Tertiary fossil discovered preserved in Baltic amber. The fly was quite small, with size of 1–3 mm (0.04–0.12 in). Fossils of the family Mythicomyiidae are relatively rare, with those preserved in amber even harder to find. The reason for the scarceness of the fossil material is presumed to be the humidity of the Baltic region throughout the Tertiary, which made the region unsuited to the aridity-loving mythicomyiids.
In 2002, the species was named after the model and actress Carmen Electra by Neal Evenhuis, former president of the International Commission on Zoological Nomenclature and senior entomologist at the Hawaii Biological Survey. Evenhuis attempted to contact the model to inform her about the naming of Carmenelectra shechisme, but his efforts were unsuccessful. In 2008, he said: "The offer's still good. I'll be willing to meet her." Names of species discovered in amber (such as the genus Electromyrmococcus) often contain the prefix electro- (ἤλεκτρον (elektron) meaning "amber" in Greek). The species epithet is reminiscent of the Victorian entomologist George Willis Kirkaldy's alleged practise of commemorating his romantic conquests with names of women. The official description of the species says: "The genus-group name is named for television, film, and magazine personality, Carmen Elektra [sic]. Both namesakes exemplify splendid somal structure for their respective taxa. The species-group epithet is an arbitrary combination of letters."