Nemegtomaia is estimated to have been around 2 m (7 ft) in length, and to have weighed 40 kg (85 lb), a size extrapolated from more completely known relatives. As an oviraptorosaur, it would have been feathered. The neural spines of the neck (cervical) vertebrae were short, and the neural arches had an x-shaped appearance. The middle three of these vertebrae were the largest. The scapula (shoulder blade) appears to have been 185 mm (7 in) in total length. The humerus (upper arm bone) had a fossa (depression) in a position similar to modern birds, but atypical among oviraptorosaurs, and appears to have been 152 mm (6 in) long. The radius of the lower arm was straight, oval in cross-section, and may have been 144 mm (5 in) long. The first finger was relatively large and had a strong ungual (claw bone), and was more massive than the two other fingers. The second finger was slightly longer than the first, and the third finger was the smallest. The upper margin of the ilium of the pelvis was straight, and though both ilia were close to each other, they were not fused together. The pubic shaft was turned backwards. The femur (thigh bone) is estimated to have been 286 mm (11 in) long, and the tibia of the lower leg 317 mm long (12 in).
The skull of Nemegtomaia was deep, narrow, and short (compared to the rest of the body), and reached 179 mm (7 in) in length. It had a well-developed crest, formed by the nasal and premaxilla bones (mainly the latter) of the snout. The nearly vertical front margin of the holotype's crest formed an almost 90 degree angle with the upper margin of the skull. Compared to other oviraptorids, the nasal processes (projections) of the premaxillae were barely visible when viewed from above (where they connected with the nasal bones on the highest points of the crest). The crest extended hindwards and down, forming a round arch at the highest point. The diameter of the orbit (eye opening) was 52 mm (2 in); the eyes looked large due to the shortness of the skull. The antorbital cavity in front of the eye consisted of two fenestrae (openings); a large antorbital fenestra at the back, and a small maxillary fenestra at the front. Nemegtomaia was distinct from other oviraptorids in that the frontal bone on the midline of the skull was about 25% the length of the parietal bone from front to back. The nares (external nostrils) were relatively small and placed high on the skull.
Preserved parts and reconstruction of specimen MPC-D
The jaws of Nemegtomaia were toothless, and like other oviraptorid dinosaurs, it had a short snout with a deep, robust, and somewhat parrot-like beak. It had a hard palate formed by the premaxillae, vomers, and maxillae, like other oviraptorids. The palate was strongly concave (downwards-projecting), and had a cleft on the central part. As in other oviraptorids, it had a pair of tooth-like projections on the palate that were directed downwards (a feature that has been called "pseudo-teeth"). Nemegtomaia had small foramina (openings) on the sides of the suture (joint) between the premaxillae at the front of the snout, which may have been nutrient openings (and which indicate the presence of a keratinous bill). The lower jaw was short and deep, with a convex lower surface, and reached 153 mm (6 in) in length. The dentary bone of the lower jaw reached 50 mm (2 in) at its highest point. The mandibular symphysis (where the two-halves of the lower jaw connected) was short, deep, and very pneumatised (with air-spaces). The mandibular fenestra was large and was located at the front part of the lower jaw. As in most other oviraptorids, the front of the lower jaw was down-turned.
Though Nemegtomaia does not possess any single feature that distinguishes it from other oviraptorids (autapomorphies), the combination of a crest, an enlarged first finger, and a high number of sacral vertebrae (eight), is unique to this taxon.