The fossil ant Titanomyrma lubei was discovered in ancient lake sediments in the DMNS locality 784, Farson Fish Beds, Laney Member of the Green River Formation; Sweetwater County, Wyoming, USA by Louis Lube, the collector and donor of the holotype specimen.
The fossil is part of the collection of Denver Museum of Nature and Science and was discovered by Bruce Archibald and co-author and museum chief curator Kirk R. Johnson while casually going through storage drawers. The fossil depicts the queen ant only and no fossils of workers have been found. With the discovery of Titanomyrma lubei and the description of the genus, two other species of giant ants, Formicium gigantea and Formicium simillima, were reclassified into this genus.
Well preserved fossils of Titanomyrma giganteum and Titanomyrma simillima were discovered in the Messel shales, near the village of Messel, in the state of Hesse, 30 km south of Frankfurt am Main (Darmstadt Administrative District), in Germany. A related undescribed species has been found in the nearby Eckfeld Maar.
The name of the genus is a derivative of the Greek Τιτάν (Titan), meaning 'one of prodigious size, strength, or achievement', and alluding to the Titans of Greek mythology; and the Greek word μύρμηξ (myrmex) meaning 'ant', gender feminine. The specific epithet of the new species is formed from the surname of the collector of the holotype, Louis Lube.