In this paper, we show exceptional three-dimensionally preserved fossilized muscle tissues in 380-384 Myr old placoderm fish (Late Devonian), offering new morphological evidence supporting the hypothesis that placoderms are the sister group to all other gnathostomes. We describe the oldest soft tissue discovered in gnathostomes, which includes striated muscle fibres, circulatory and nerve tissues, preserved as phosphatized structures precipitated by microbial infilling of small, protected areas under the headshield of the arthrodire, Eastmanosteus calliaspis. Muscle impressions have also been found in the ptyctodontid, Austroptyctodus gardineri. The specimens display primitive vertebrate muscle structures; in particular, shallow W-shaped muscle blocks such as those observed in lampreys. New information from fossilized soft tissues thus elucidates the affinities of the placoderms and provides new insights into the evolution and radiation of gnathostomes.