The morphological traits of the Carboniferous coleoids were analyzed to discover re-occurring combinations of different characteristic features during the early evolution of coleoid cephalopods. The early coleoid evolution in the Carboniferous is characterized by (1) a complex mosaic combination of the "old" and "new" morphological traits, (2) the parallel appearance and variations of new morphological features, and (3) relatively rapid changes in basic morphology. A mosaic combination is exemplified with Donovaniconus, which possesses a body chamber (bactritoid trait), a pro-ostracum-like structure (a novelty), and an ink sac (coleoid trait), or Mutveiconites, which combines a body chamber (bactritoid trait) and a rostrum (coleoid trait). A novelty or new feature can appear at any evolutionary stage, but "old" traits can continue to exist for a long period after the appearance of a novelty in another form. An example of this phenomenon is demonstrated by the evolutionary loss of the body chamber in the Lower Carboniferous (ca. 325 MY) taxon Hematites, which is the earliest recorded coleoid, and the retention of the body chamber in the Late Carboniferous (ca. 290 MY) taxa Shimanskya, Mutveiconites, Donovaniconus, and Saundersites. The parallel appearance of new morphological traits is illustrated by the appearance of the massive rostrum in the Early Carboniferous Hematites and the development of a cap-like small loosely calcified rostrum in the Late Carboniferous Mutveiconites.