The holotype, IGM 100/84, was collected in the Bayan Shireh Formation (=Baynshirenskaya) in Khara Khutul, southeastern Mongolia, dating from the Cenomanian and the Turonian stages, around 98-89.3 million years ago. It was first reported in 1979. It consists of a partial skeleton, lacking the skull, which includes a nearly complete pelvis with part of the right ischium missing.
The type species, Enigmosaurus mongoliensis, was named in 1983, by Rinchen Barsbold and Altangerel Perle. The generic name was stated to be derived from Greek αἴνιγμα, ainigma, "riddle", after the puzzling and unusual shape of its pelvis (hips); at the time little was known about therizinosauroids. The specific name refers to the provenance from Mongolia.
Enigmosaurus reached a length of five to seven metres, and a weight of one tonne. It is a considerably larger dinosaur than the related Erlikosaurus. The obturator process on the front edge of the ischium is horizontally elongated and low.
Enigmosaurus was by the describers assigned to a separate Enigmosauridae but later considered a member of the Segnosauridae which are today called the Therizinosauridae. Lindsay Zanno in 2010 recovered a position more basal in the Therizinosauroidea.