Representatives of the avian taxon Zygodactylidae are among the most abundant small arboreal birds in the early Palaeogene of the Northern Hemisphere. Still, however, the osteology of these birds, which have recently been shown to be the sister taxon of the Passeriformes, is only incompletely known. Here we describe a new species of Primozygodactylus from the middle Eocene of Messel in Germany. The holotype specimen of P. eunjooae sp. nov. for the first time allows a detailed examination of the distal tarsometatarsus in one of the Messel zygodactylids. It also exhibits exceptionally well-preserved tail feathers which, most notably, are formed by a long central pair of rectrices. We further report on a new specimen of Primozygodactylus major, which is the largest zygodactylid from Messel. Being one of the few dissociated skeletons of Primozygodactylus, the new specimen shows some previously unknown osteological features of this taxon and allows a more detailed comparison with other zygodactylids.