We report a new specimen of the extinct procellariiform species Diomedeoides brodkorbi (Aves, Diomedeoididae) from the early Oligocene (Rupelian) of Rheinweiler in southwestern Germany. The well-preserved partial skeleton allows the recognition and reassessment of new osteological details that bear on the phylogenetic affinities of diomedeoidids. The presence on the coracoid of a deeply excavated, cup-like facies articularis for the scapula suggests a stem group position of the Diomedeoididae within Procellariiformes, because this trait also occurs in stem-group representatives of several avian groups, as well as in Mesozoic non-neornithine birds, and is a plesiomorphic character. We hypothesize that the similarities of Diomedeoides to extant southern storm-petrels (Oceanitinae), such as the long mandibular symphysis, the small processus supracondylaris dorsalis and the long legs are plesiomorphic for Procellariiformes.