Pleurojulid millipedes, known since the turn of the last century to be relatively abundant in the Westphalian D (Carboniferous: Pennsylvanian) Gaskohl of Nýřany, Czech Republic, are here also identified as an important component of the Pennsylvanian (Westphalian D) Mazon Creek millipede fauna preserved in ironstone nodules. Pleurojulids reach lengths approaching 10 cm, have as many as 69 body segments, medium-sized heads, and large ocellaria with upwards of 40 ocelli. Pleurojulids have previously been interpreted as having either a juliform-like or a colobognathan-like trunk-ring architecture. In order to distinguish between these two hypotheses, almost all pleurojulid specimens in museum collections were surveyed to document the deformation pattern of exoskeletal elements to aid in reconstruction of the trunk-ring architecture. The Nýřany specimens are completely flattened while the Mazon Creek specimens retain a degree of three-dimensionality. In order to assess how trunk-ring architecture controls patterns of deformation, a variety of extant millipedes were experimentally compressed. The distribution of exoskeletal elements in pleurojulid fossils was most similar to that seen in compressed extant polyzoniid millipedes. Based on the available evidence, pleurojulid trunk-ring architecture is reconstructed as semicircular in cross section, consisting of arched diplotergites, free pleurites firmly articulated to the lateral margins of the tergites and held in a near horizontal position, and free sternites. Pleurojulida are hypothesized to be basal helminthomorph, the sister group to Colobognatha, though inclusion in Helminthomorpha is equivocal. The taxonomy of previously described pleurojulid millipedes from Nýřany is revised and newly recognized specimens from Mazon Creek specimens are described. Two genera are recognized within the new order Pleurojulida: Pleurojulus and Isojulus. Two species of Pleurojulus are recognized: P. biornatus and P. levis. Pleurojulus aculeatus and P. pinguis are synonymized with P. levis. Only one species of Isojulus, I. constans, is recognized with I. setipes, I. marginatus synonymized with it along with Pleurojulus longipes and P. falcifer.