Desconhecido.
Tolkien não escreveu extensas histórias sobre o povo de Harad, então é difícil dizer com certeza quando seus reinos foram estabelecidos. É possível, no entanto, que fosse tão cedo quanto a Primeira Era; o Silmarillion publicado estabelece que os homens estavam viajando para o sul em seus primeiros dias:
At the first rising of the Sun the Younger Children of Ilúvatar awoke in the land of Hildórien in the eastward regions of Middle-earth; but the first Sun arose in the West, and the opening eyes of Men were turned towards it, and their feet as they wandered over the Earth for the most part strayed that way.
[...]
West, North, and South the children of Men spread and wandered, and their joy was the joy of the morning before the dew is dry, when every leaf is green.
The Silmarillion III Quenta Silmarillion Chapter 12: "Of Men"
Como revelado em um dos mapas de Ambarkanta , Hildórien está no limite mais oriental da Terra-média; ao sul disso é necessariamente Harad.
No entanto, a menção cronologicamente mais antiga de Harad I pode encontrar é c. S.A. 2000, em uma entrada em:
2000-3000 The Númenórean now make permanent dwellings on the shores of Middle-earth, seeking wealth and dominion; they build many havens and fortresses. The Elf-friends go chiefly to the North-west, but their strongest place is at Pelargir above the Mouths of Anduin. The King's Folk establish lordships in Umbar and Harad and in many other places on the coasts of the Great Lands.
History of Middle-earth XII The Peoples of Middle-earth Chapter 6: "The Tale of Years of the Second Age"
No entanto, é possível que isso se refira ao subcontinente de Harad, ao invés das nações dos Haradrim. A primeira referência que posso encontrar para o último é de quase o final da Segunda Era, quando Sauron está se preparando para a sua guerra final (ênfase minha):
Now Sauron prepared war against the Eldar and the Men of Westernesse, and the fires of the Mountain were wakened again. Wherefore seeing the smoke of Orodruin from afar, and perceiving that Sauron had returned, the Númenóreans named that mountain anew Amon Amarth, which is Mount Doom. And Sauron gathered to him great strength of his servants out of the east and the south; and among them were not a few of the high race of Númenor. For in the days of the sojourn of Sauron in that land the hearts of well nigh all its people had been turned towards darkness. Therefore many of those who sailed east in that time and made fortresses and dwellings upon the coasts were already bent to his will, and they served him still gladly in Middle-earth. But because of the power of Gil-galad these renegades, lords both mighty and evil, for the most part took up their abodes in the southlands far away; yet two there were, Herumor and Fuinur, who rose to power among the Haradrim, a great and cruel people that dwelt in the wide lands south of Mordor beyond the mouths of Anduin.
The Silmarillion V Of the Rings of Power and the Third Age