They (like we) are cousins to the Elves. First, from Tolkien's Letters
I suppose that actually the chief difficulties I have involved myself in are scientific and biological - which worry me just as much as the theological and metaphysical (though you do not seem to mind them so much). Elves and Men are evidently in biological terms one race, or they could not breed and produce fertile offspring - even as a rare event: there are 2 cases only in my legends of such unions, and they are merged in the descendants of Earendil.
Tolkien quite correctly notes that at least as far as biology is concerned, Elves and Men are one species. (Thanks to @Shamshiel for finding this excellent quote!)
And in LotR, Tolkien says:
It is plain indeed that in spite of later estrangement Hobbits are relatives of ours: far nearer to us than Elves, or even than Dwarves.
So Men, Hobbits and Elves (and maybe Dwarves) are all a single species. In our world this would mean they had a common ancestor, but the Silmarillion makes clear that Elves and Men (and presumably Hobbits) were created separately, but were a single species.
The Elves came first:
It is told that even as Varda ended her labours, and they were long, when first Menelmacar strode up the sky and the blue fire of Helluin flickered in the mists above the borders of the world, in that hour the Children of the Earth awoke, the Firstborn of Iluvatar. By the starlit mere of Cuivinen, Water of Awakening, they rose from the sleep of Iluvatar;
Men came later:
Now the Children of Iluvatar are Elves and Men, the Firstborn and the Followers.
Elves awoke in the darkness of Middle Earth while Valinor was still lit by the light of the Two Trees. Many of the Elves followed Orome to Valinor and lived there for ages before the Noldor rebelled and returned to Middle-Earth. It was at that time, after the Darkening of Valinor, that the Sun and the Moon were fashioned with the last light of the Trees. The Sun rose for the first time just as the Noldor returned to Middle Earth and
At the first rising of the Sun the Younger Children of Iluvatar awoke in the land of Hildrien in the eastward regions of Middle-earth;
So Elves predated men by uncounted centuries.
As far as I know, Tolkien never stated whether Men and Hobbits were created separately and arose at different times or places or if the close to ten thousand years between the awakening of Men and the first glimpse we have of Hobbits was long enough for them to have naturally evolved their small stature, furry feet and longer lifetimes.
But, regardless, we're all the same species.
