Paired fins are a major innovation1,2 that evolved in the jawed vertebrate lineage after divergence from living jawless vertebrates3. Extinct jawless armoured stem gnathostomes show a diversity of paired body-wall extensions, ranging from skeletal processes to simple flaps4. By contrast, osteostracans (a sister group to jawed vertebrates) are interpreted to have the first true paired appendages in a pectoral position, with pelvic appendages evolving later in association with jaws5. Here we show, on the basis of articulated remains of Tujiaaspis vividus from the Silurian period of China, that galeaspids (a sister group to both osteostracans and jawed vertebrates) possessed three unpaired dorsal fins, an approximately symmetrical hypochordal tail and a pair of continuous, branchial-to-caudal ventrolateral fins. The ventrolateral fins are similar to paired fin flaps in other stem gnathostomes, and specifically to the ventrolateral ridges of cephalaspid osteostracans that also possess differentiated pectoral fins. The ventrolateral fins are compatible with aspects of the fin-fold hypothesis for the origin of vertebrate paired appendages6,7,8,9,10. Galeaspids have a precursor condition to osteostracans and jawed vertebrates in which paired fins arose initially as continuous pectoral–pelvic lateral fins that our computed fluid-dynamics experiments show passively generated lift. Only later in the stem lineage to osteostracans and jawed vertebrates did pectoral fins differentiate anteriorly. This later differentiation was followed by restriction of the remaining field of fin competence to a pelvic position, facilitating active propulsion and steering.