We describe a new species of Early Cretaceous bird from the Yixian Formation of Liaoning Province. Xinghaiornis lini gen. et sp. nov. is relatively large and characterized by a long, toothless rostrum and an elevated pedal digit I. The design of the skull and feet suggests that this bird was likely a mud-prober. This discovery provides strong support indicating that this avian trophic specialization originated at least 125 million years ago.