First mentioned in the Hypatian Codex under 1252 as Novogorodok (i.e. "new little town") the town was a major settlement in the remote western lands of the Krivichs that came under the control of the Kievan Rus at the end of the 10th century. Later hypothesis is disputed, as there are earliest archaeological findings from 11th century only.
In the 13th century, the fragile unity of the Rus disintegrated due to nomadic incursions from Asia, which reached a climax with the Mongol Horde's sacking of Kiev (1240), leaving a geopolitical vacuum in the region, which was known as Black Ruthenia at the time. The Early East Slavs splintered along preexisting tribal lines into a number of independent and competing principalities.
Mindaugas of Lithuania made use of the plight to annex Navahrudak, which also became part of Kingdom of Lithuania , later Grand Duchy of Lithuania. During the 16th century, Maciej Stryjkowski was the first who, in his chronicle , proposed theory, that Navahrudak became the capital of the 13th century state. This statement is supported by several other scholars, while others dispute this notion, mainly because contemporary chronicles of the 13th century do not give any reference about Navahrudak as capital, even stating that city was transferred to the king of Halych-Volhynia . Vaišvilkas, the son and successor of Mindaugas, took monastic vows in Lavrashev Monasterynear Novgorodok and founded an Orthodox convent there.
Navahrudak was a part of the Polish-Lithuanian Commonwealth following the Union of Lublin in 1569. In 1795 it was incorporated into Grodno Governorate of Imperial Russia due to the Partitions of Poland. In the First World War, it was under German occupation from 1915 to 1918, and was occupied by the Polish Army at first, later the Red Army, during the Polish-Bolshevik war. It was returned to Poland by the treaty of Riga, following which Navahrudak became the capital of Nowogródek voivodship.
Soviet troops entered the city in September 1939 and it was annexed into the Byelorussian SSR. In the administrative division of the new territories, the city briefly (2nd of November to 4th of December) was the centre of the Navahrudak Voblast. Afterwards the administrative centre moved to Baranavichy Voblast, the city became the centre of the Navahrudak Raion (15th of January 1940). On the 22nd of June 1941 Nazi Germany invaded the USSR and Navahrudak was occupied on the 4th of July following one of the more tragic events when the Red Army was surrounded in what's known as the Novogrudok Cauldron. Prior to the war, the population was 20,000, of which about half were Jewish. During a series of "actions," the Germans killed all but 550 of the approximately 10,000 Jews. Those not killed were sent into slave labor.
During the German occupation it became part of the Ostland. Partisan resistance immediately began, with most famous Bielski partisans made of Jewish volunteers operated in the region. The Red Army liberated the city almost exactly three years after its occupation on 8th July 1944. During the war more than 45 thousand people were killed in the city and in the surrounding area, and over 60% of housing was destroyed.
After the war, the BSSR retained the city, and a rapid rebuilding process quickly restored most of the destroyed infrastructure. On 8th of July 1954, following the disestablishment of the Baranavichy Voblast, the rajon, along with Navahrudak became part of the Hrodna Voblast, in which it remains to this day, in modern Belarus.
Navahradak was an important shtetl and home to the Harkavy Jewish family, including Alexander Harkavy. Some of the Harkavy are buried at the old Jewish cemetery of Navahrudak. A house is shown where the poet Adam Mickiewicz was born; there are also his statue and the "Mound of Immortality", created in his honour by the Polish administration in 1924–31.