Tiny sinuous trace fossils have been found within probable gut contents of an exceptionally preserved specimen of a hadrosaurid dinosaur, Brachylophosaurus canadensis, from the Judith River Formation of Montana. Approximately 280 examples of the trace fossils were observed in 19 samples of gut region material. The tubular structures typically are about 0.3 mm across. Many have thin calcareous linings or layers, and some exhibit fine surficial striae. At least two dozen of these trace fossils share walls with adjacent tubular traces, and this association can extend for several millimeters. While the trace fossils share some characteristics with fine rhizoliths, these features are most consistent with tiny burrows, or possibly body impressions, of worms (vermiform organisms) of uncertain biologic affinity. Such trace fossils have not been reported previously, and herein described as Parvitubulites striatus n. gen. n. sp. Either autochthonous (parasites) or allochthonous (scavengers) worms may have created the trace fossils, but taphonomic factors suggest that autochthonous burrowers are more likely. Several lines of evidence, such as constant diameters and matching directional changes, suggest that the paired trace fossils were made by two individuals moving at the same time, which implies sustained intraspecific contact. Parvitubulites striatus provides a rare record of interactions between terrestrial, meiofaunal-sized, soft-bodied invertebrates and a dinosaur carcass. The evidence that the worms may have parasitized a living hadrosaur and subsequently left traces of intraspecific behavior between individual worms adds unique information to our understanding of Mesozoic trophic interactions.