The legend originated perhaps from the time when their ancestors, the Éothéod saw and knew the Hobbits from the Vales of Anduin, before or around their Wandering Days. From 'Holbytla' the word 'Hobbit' in Westron was derived.
There is only one tale about them, namely that they do not appear in any other tales. They do little, and avoid the sight of men, being able to vanish in a twinkling; and they can change their voices to resemble the piping of birds.
When Théoden met Peregrin Took and Meriadoc Brandybuck standing guard at Isengard on 5 March, T.A. 3019, he immediately connected them to the folklore creature although he noted that they weren't known to spout smoke from their mouths. He was corrected by Peregrin, who said that they preferred the term "Hobbit" (kuduk).
Holbytla seems to be a retroactive etymology, invented to explain the word "hobbit", which of course was initially a spontaneous inspiration by Tolkien without an explanation behind it.