The size of S. altus is estimated as about 4.3 metres (14 ft) long and 1.4 metres (4.6 ft) tall at the hips, with a weight of around 150 kilograms (330 lb).
Struthiomimus had a build and skeletal structure typical of ornithomimids, differing from closely related genera like Ornithomimus and Gallimimus in proportions and anatomical details. As with other ornithomimids, they had small slender heads on long necks (which made up about 40% of the length of the body in front of the hips). Their eyes were large and their jaws were toothless. Their vertebral columns consisted of ten neck vertebrae, thirteen back vertebrae, six hip vertebrae, and about thirty-five tail vertebrae. Their tails were relatively stiff and probably used for balance. They had long slender arms and hands, with immobile forearm bones and limited opposability between the first finger and the other two. As in other ornithomimids but unusually among theropods, the three fingers were roughly the same length, and the claws were only slightly curved; Henry Fairfield Osborn, describing a skeleton of S. altus in 1917, compared the arm to that of a sloth. These might have been adaptations to support wing feathers.
Struthiomimus differed from close relatives only in subtle aspects of anatomy. The edge of the upper beak was concave in Struthiomimus, unlike Ornithomimus, which had straight beak edges. Struthiomimus had longer hands relative to the humerus than other ornithomimids, with particularly long claws. Their forelimbs were more robust than in the similar Ornithomimus.