Problematic fossils, extinct taxa of enigmatic morphology that cannot be assigned to a known major group, were once a major issue in palaeontology. A long-favoured solution to the 'problem of the problematica', particularly the 'weird wonders' of the Cambrian Burgess Shale, was to consider them representatives of extinct phyla. A combination of new evidence and modern approaches to phylogenetic analysis has now resolved the affinities of most of these forms. Perhaps the most notable exception is Tullimonstrum gregarium, popularly known as the Tully monster, a large soft-bodied organism from the late Carboniferous Mazon Creek biota (approximately 309-307 million years ago) of Illinois, USA, which was designated the official state fossil of Illinois in 1989. Its phylogenetic position has remained uncertain and it has been compared with nemerteans, polychaetes, gastropods, conodonts, and the stem arthropod Opabinia. Here we review the morphology of Tullimonstrum based on an analysis of more than 1,200 specimens. We find that the anterior proboscis ends in a buccal apparatus containing teeth, the eyes project laterally on a long rigid bar, and the elongate segmented body bears a caudal fin with dorsal and ventral lobes. We describe new evidence for a notochord, cartilaginous arcualia, gill pouches, articulations within the proboscis, and multiple tooth rows adjacent to the mouth. This combination of characters, supported by phylogenetic analysis, identifies Tullimonstrum as a vertebrate, and places it on the stem lineage to lampreys (Petromyzontida). In addition to increasing the known morphological disparity of extinct lampreys, a chordate affinity for T. gregarium resolves the nature of a soft-bodied fossil which has been debated for more than 50 years.