Carmenelectra is known from a Tertiary fossil discovered preserved in Baltic amber. The fly was very small, with size ranging from 1–3 millimetres (0.039–0.12 in). The fossils of the family Mythicomyiidae are relatively rare, with those preserved in amber even harder to find. It is presumed that the reason for the scarceness of the fossil material is the humidity of the Baltic region during 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 practice 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."
- Evenhuis, Neal L. (2002). "Review of the Tertiary microbombyliids (Diptera: Mythicomyiidae) in Baltic, Bitterfeld, and Dominican amber". Bishop Museum. http://mapress.com/zootaxa/2002f/z00100f.pdf. Retrieved 25 January 2013.
- Leber, Jessica (4 March 2008). "The latest in newly discovered species: You pay for it, you get to name it". University of Columbia. http://jscms.jrn.columbia.edu/cns/2008-03-04/leber-nameaspecies.html. Retrieved 25 January 2013.
- The Nabokovian, Issues 56-59. Vladimir Nabokov Society. 2006.