Some probe-foraging birds locate their buried prey by detecting mechanical vibrations in the substrate using a specialised tactile bill-tip organ comprising mechanoreceptors embedded in densely clustered pits in the bone at the tip of their beak. This remarkable sensory modality is known as “remote-touch”, and the associated bill-tip organ is found in probe-foraging taxa belonging to both the paleognathous (in kiwi) and neognathous (in ibises and shorebirds) clades of modern birds. Intriguingly, a structurally similar bill-tip organ is also present in the beaks of extant, non-probing paleognathous birds (e.g. emu and ostriches) that do not use remote-touch. By comparison with our comprehensive sample representing all orders of extant modern birds (Neornithes), we provide evidence that the lithornithids (the most basal known paleognathous birds which evolved in the Cretaceous period) had the ability to use remote-touch. This finding suggests that the occurrence of the “vestigial” bony bill-tip organ in all modern non-probing paleognathous birds represents a plesiomorphic condition. Furthermore, our results show that remote-touch probe-foraging evolved very early among the Neornithes and it may even have predated the paleognathous-neognathous divergence. We postulate that the tactile bony bill-tip organ in Neornithes may have originated from other snout tactile specializations of their non-avian theropod ancestors.