Calenardhon was the first name of the lands of Rohan, when it was still a part of the kingdom of Gondor. The name, in Sindarin, means 'the Green Region,' or, 'the Green Province,' and was an area of great, grassy, sparsely-populated plains west of Anórien and to the north of the White Mountains.
This area of Gondor was an area of constant incursion, and, during the reign of the Steward Cirion, it came under attack from the Balchoth. In order to drive back the invaders, Gondor called upon the Éothéod for aid; the horsemen, under Eorl the Young, were successful in vanquishing the enemy at the Field of Celebrant.
After the battle, what would become the people of the Rohirrim were ceded these lands by Cirion in return for their assistance in guarding the northern marches, as well as the Gap of Rohan, against invaders.