The mandibulate euarthropods are the most speciose animal group, but the evolutionary gaps in origin of mandibulate body plan remain unresolved. Marrellomorphs, a common Paleozoic euarthropod group, had a long evolutionary history from Cambrian to Devonian. With computed microtomography, here we report the fine-scale soft-bodied morphoanatomy of the oldest marrellomorph Primicaris larvaformis, a millimeters-sized euarthropod from the similar to 518-million-year-old Chengjiang biota, China. Primicaris possesses a body plan featuring morphologically similar post-antennular biramous appendages, but also mandibulate diagnostic features including multi-segmented exopodites, a well-developed and differentiated hypostome-labrum complex, and a pancrustacean-like topological configuration of frontalmost three pairs of appendages. Phylogenetic analysis resolves Acercostraca and Marrellida as stem-Mandibulata. The undifferentiated post-antennular appendages in Primicaris suggest a possibility that the head appendages acquired a crown-mandibulate configuration before their morphological specialization in mandibulate origin. The emergence of novel appendage morphotypes in Acercostraca and Marrellida reveals that the complexity of limb tagmatization evolved independently in different Euarthropoda clades.