Энергия, благодаря которой Харемхеб достиг высокого положения, немедленно сказалась в том, как он проявлял себя в нем. Он принялся энергично восстанавливать в стране правильную организацию, которой она некогда обладала. Пробыв не менее двух месяцев в Фивах, во время которых он приводил там в порядок свои дела и привлекал еще больше на свою сторону жреческую партию тем, что присутствовал на религиозных празднествах, Харемхеб отплыл на север для преследования той же задачи. «Его величество отплыл вниз по реке… Он ввел порядок в стране, он укрепил ее, как было во времена Ра» (когда солнечный бог был фараоном). В то же время он не забывал храмов, остававшихся запертыми, пока главенствовал Атон. «Он восстановил храмы от болот Дельты до Нубии. Он сделал их (богов) изображения в большем количестве, чем прежде, умножая красоту в том, что он делал… Он воздвиг им храмы; он сделал сотни изображений, правильно воспроизведя их тела и (украсив их) всевозможными чудными драгоценными камнями. Он восстановил рубежи богов в областях этой страны, он обставил их так, как это было испокон века. Он установил для них ежедневные приношения. Все сосуды в их храмах были сделаны из серебра и золота. Он назначил в них жрецов и священнослужителей и отборные войска. Он даровал им земли и скот с полным снаряжением». Наряду с другими работами царь воздвиг статую, свою собственную и своей жены, в храме Гора в Алебастронполе, на которой откровенно описал, каким образом он постепенно возвысился из положения простого царского чиновника до престола фараонов. Таким образом, Амон получил свои прежние вклады, и доходы всех обездоленных храмов были восстановлены. Народ снова стал открыто поклоняться бесчисленным богам, что в продолжение главенства Атона он делал втайне. Скульпторы царя были разосланы по всей стране для продолжения реставрации, начатой Тутанхамоном, и для восстановления имен богов, обесчещенных и стертых Эхнатоном на обезображенных им памятниках. Снова и снова появляются в храме Амона в Карнаке отчеты о подобных реставрациях по повелению Харемхеба. Все это должно было обеспечить ему единодушную поддержку жреческой партии по всей стране. В то же время почитание Атона, хотя и не запрещенное, во многих местах подавлялось путем разрушения его святилищ. В Фивах Харемхеб срыл до основания храм Атона и употребил материал на постройку двух пилонов с южной стороны храма Амона, не использованные же им материалы были употреблены для подобных же работ его преемниками. Среди разрушенных пилонов Амона в Карнаке можно найти в настоящее время обломки святилища Атона, все еще несущие на себе имена его отверженных почитателей. Харемхеб послал также в Ахетатон за материалами храма Атона, годными для его построек. Всюду с именем ненавистного Эхнатона поступали так же, как он сам с именами богов. Его гробница в Ахетатоне была разрушена, рельефы в ней изрублены, и гробницы его вельмож в том же месте были обесчещены подобным же образом. Сделано было все, чтобы уничтожить малейшие следы царствования этого человека, и, когда в официальном делопроизводстве нужно было цитировать документы или акты из его царствования, его называли «преступником из Ахетатона».
Торжество Амона было полное, и как некогда фавориты Эхнатона воспевали счастливую судьбу последователей Атона, так теперь придворные Харемхеба, ясно поняв новые веяния, пели: «Как обильны владения того, кому ведомы дары этого бога (Амона), царя богов! Мудр тот, кто знает его, счастлив тот, кто служит ему, обретает покровительство тот, кто следует ему». Жрец Амона Неферхотеп, произносивший эти слова, получал в этот момент богатейшие знаки царского благоволения. Подобные люди прославляли падение врагов Амона в таких словах: «Горе тому, кто нападает на тебя! Твой град существует, а нападавший на тебя – низвергнут. Тьфу (sic) на того, кто грешит против тебя, где бы то ни было… Солнце того, кто тебя не знал, закатилось, а того, кто знает тебя, – сияет. Святилище того, кто нападал на тебя, лежит разрушенным во мраке, а вся земля – озарена светом».