Easterlings were mentioned under the same name for several ages, from the First Age to the Third. (Or even Fourth) But I guess it would be a rather safe assumption to say that they all had the same ancestry. In the 1st Age, Men which had sided with Morgoth (the First Dark Lord) were collectively known as Easterlings. Famous Easterlings of the First Age are Ulfang the Black and his sons, Uldor, Ulfast and Ulwarth. These are the guys who betrayed the Noldor (Elves in Exile) in their war. One other named Easterling included Brodda who enslaved Hurin's people.
Hurin was an Edain, by the way, a word which means 'late-comers' (because men woke later after Genesis) , but was more often used to describe Men which are Elf-friends. All Men were said to have some sort of encounter with Morgoth very early on, since He wanted to enlist their services against the Eldar. But the Edain escaped Morgoth and reached the Elves. Easterlings, on the other hand, remained in his service, although some like the sons of Bor, changed his allegience to follow the Elves. Easterlings also arrived in Beleriand, which was in the West continent, later than the Edain, which showed that they had originated in the East...
Majority of those Easterlings that followed Morgoth either perished or fleed Beleriand after the downfall of Morgoth at the end of the First Age. The Men of Numenor (The Numenoreans) had Elf-friend Ancestry, and were granted Numenor (Atlantis) for their aid against Morgoth. Of course, that means that the Good Guys had their paradise, while the Bad Guys wallow in their guilt and ate worms in the East. The rise of Sauron reversed the situation somewhat; the Men of Numenor became proud and scared of Death, which enabled Sauron to corrupt them into invading Valinor (Land of the Gods). The result is Zeus destroying Atlantis
, leaving only a remnant of those Numenoreans (the Faithful) who escaped to Middle-Earth.
Meanwhile, of course, the Easterlings and Haradrim and other 'Wild Men' were happily dancing around the fire and were none too happy that the Numenoreans had come back again to Middle-Earth. Previously, of course, the Numenoreans had invaded their lands while making war against Sauron. The Numenoreans probed up their pretty kingdoms, Arnor and Gondor, and war sparked. Sauron had returned into the fray, and then, everyone just fought until Isildur hacked out Sauron's finger.
Yep, that about summarised the ongoings between the Easterlings and the Edain. Major potholes, of course - making of the Nine rings, capturing of Sauron, but the essense is there. So you see, there was B-A-D blood between the two people (Prof T always liked to trace enmity from the beginning).