The evolutionary history of aquatic invasion in birds would be incomplete without incorporation of extinct species. We show that aquatic affinities in fossil birds can be inferred by multivariate analysis of skeletal features and locomotion of 245 species of extant birds. Regularized discriminant analyses revealed that measurements of appendicular skeletons successfully separated diving birds from surface swimmers and flyers, while also discriminating among different underwater modes of swimming. The high accuracy of this method allows detection of skeletal characteristics that are indicative of aquatic locomotion and inference of such locomotion in bird species with insufficient behavioural information. Statistical predictions based on the analyses confirm qualitative assessments for both foot-propelled (Hesperornithiformes) and wing-propelled (Copepteryx) underwater locomotion in fossil birds. This is the first quantitative inference of underwater modes of swimming in fossil birds, enabling future studies of locomotion in extinct birds and evolutionary transitions among locomotor modes in avian lineage.