Першыя звесткі пра гербы Навагрудка змяшчаюцца ў гербоўніку польскага геральдыста XVI ст.Барташа Папроцкага, у якім гаворыцца, што «ваяводства Наваградскае ўжывае за герб анёла чорнага ў полі чырвоным, горад Наваградак ужывае за герб Пагоню, пры якой ёсць Замак». Праз пэўны час з герба знік замак, i абодва гербы (з чорным анёлам i Пагоняй) пачалі лічыць ваяводскімі. У канцы XVI ст. з гербаў знікае і чорны анёл[1].
...печати местской на ратуш Архангела Михаила в одной раце меч, а в другой вага.
На пачатку XVIII ст. навагрудскі герб быў дапоўнены змеем-д’яблам. Расійскі варыянт герба, зацверджаны ў 1845 г., у асноўным захаваў гэтую ж кампазіцыю, толькі з некаторымі зменамі (архангел павярнуў меч вастрыём на змея, у якога зніклі крылы)[1].
У 1857 г. Расійскі дэпартамент геральдыкі ўвёў новыя правілы складання зямельных i гарадскіх гербаў, якія прадугледжвалі выкарыстанне знешніх упрыгожанняў. Паводле гэтых правілаў у 1860-х гг. разам з праектамі гербаў больш як дзесяці беларускіх гарадоў быў складзены і новы герб Наваградка, на якім архангел быў заменены на стылізаванае крыло i руку з мечам[1].