Haremhab taucht aus der ägyptischen Geschichte zusammen mit Tut-anch-Amun auf, sofort mit umfangreichen Machtbefugnissen versehen. Er war "Stellvertreter des Königs an der Spitze der Beiden Länder", Oberbefehlshaber des Heeres, "oberster Mund des Landes", Erbfürst und Obervermögensverwalter. In diesen Positionen führte er faktisch zusammen mit Eje die Geschicke Ägyptens für den heranwachsenden Tut-anch-Amun. 

Der hier dargestellte Lebenslauf Haremhabs bleibt also bis auf wenige Belege Spekulation.
Seine Heimat war Hutnesu im 18. oberägyptischen Gau, der Horus von Hutnesu ist sein Namensgeber. Die Eltern sind nicht bekannt, und man vermutet, dass er bereits unter Amenhotep III seine militärische Karriere begann. Das Grab Nr. 24 in Amarna wird einem Pa-Aton-em-hab zugerechnet, es ist möglich, dass dies der Name ist, den Haremhab in der Amarnazeit trug.

Zusammen mit Eje war er für den Umzug der Regierung nach Memphis verantwortlich, sicher auch wegen der bedrohlichen außenpolitischen Situation und zur Vermeidung unnötiger Spannungen  mit dem Amun-Klerus in Theben. In Saqqara ließ er sich ein feudales Grab anlegen, in dem seine erste Frau Amenia bereits zu Beginn der Regentschaft Tut-anch-Amuns bestattet wurde. Auf den Reliefs wird seine Stellung über der des Eje betont.

Haremhab´s zweite Frau und spätere Königin wurde lange Zeit für eine Schwester der Nofretete namens Mutnedjmet gehalten, die damit das Bindeglied zu seinen Vorgängern herstellte und die Legitimation der Herrschaft garantieren sollte. Gegen diese Theorie  von Wolf, Hornung u.a. wenden sich jetzt Helck, Krauss, von Beckerath, van Dijk und weiter Ägyptologen, die den Namen Mutbelet lesen und eine Verbindung zum Königshaus ablehnen. Mutnedjmet/Mutbelet starb bereits am Anfang seiner Regentschaft. Der König beauftragte seinen Bauleiter Maja mit der Bestattung in Saqqara.

Im Frühjahr 1319 (1305) v. Chr. wurde Haremhab nach Eje´s Tod zum Herrscher auf dem Pharaonenthron. Seine Krönungsstele anlässlich der Opet-Festes dokumentiert die Bestätigung seiner Herrschaft durch Amun. Die Dauer dieser Regentschaft ist aber wieder umstritten: Helck gibt ihm 12 Jahre und 3 Monate, an anderer Stelle wird ein 58. Jahr belegt, hier allerdings unter Einschluss der Regierungszeiten der verfemten Könige  Echnaton - Semenchkare - Tut-anch-Amun - Eje. Unter Berücksichtigung dieser Könige ergibt sich noch immer eine Herrschaftsdauer von 27 Jahren (siehe unter Semenchkare).