Из дворян Московской губернии. В 1857 году окончил 2-й петербургский кадетский корпус. Служил в лейб-гвардии Московском полку. Участвовал в подавлении восстания 1863 года, был ранен. Последствия ранения вынудили в 1867 года оставить строевую службу. Поступил в Военно-юридическую академию в Петербурге. По окончании служил по военно-судебному ведомству, занимая должности московского и петербургского военного прокурора, виленского военного прокурора, военного судьи Петербургского военно-окружного суда (при этом значась одним из директоров Виленского губернского комитета общества попечительного о тюрьмах), председателя Виленского военно-окружного суда.
Состоял членом Военно-исторического общества.
В Петербурге посещал салоны А. П. Философовой и С. А. Толстой, общался с Н. С. Лесковым, Ф. М. Достоевским, бывал в Ясной Поляне у Л. Н. Толстого. С Навроцким был знаком военный юрист, литератор, коллекционер А. В. Жиркевич, так же, как и он, получивший образование в Военно-юридической академии и служивший в Вильне.
В 1891 году вышел в отставку с чином генерал-лейтенанта. С 1900 года член Литературно-художественного общества. В 1903 году стал одним из активных деятелей охрапнительного общественно-политического объединения «Русского собрания», впоследствии трансформировавшегося в одну из первых черносотенных организаций.
Сын Александр Александрович Навроцкий — актёр и автор пьес, опубликованных под псевд. А. А. Наровский; приписывались отцу.
Похоронен в Санкт-Петербурге на Новодевичьем кладбище.
Дебютировал светским романом «Семья Тарских» (Москва, 1869). В начале литературной деятельности в конце 1860-х — начале 1870-х сотрудничал в петербургском либеральном журнале «Вестник Европы».
В 1879—1882 годах редактор и издатель журнала «Русская речь», в котором публиковал свои статьи на общественные темы, стихотворения, исторические драмы в стихах. Привлек к сотрудничеству в журнале А. Д. Градовского, И. А. Гончарова, Н. Я. Данилевского, А. В. Круглова, Е. Л. Маркова.
Позднее печатал стихи в журналах «Русский вестник» (1903—1904), «Мирный труд» (1905, 1907), «Светоч» (1910).
Перу Навроцкого принадлежат исторические баллады, драмы в стихах, романы, рассказы, очерки, статьи. Наиболее значительное место в его творчестве занимают своего рода стихотворные иллюстрации к наиболее ярким персонажам и эпизодам русской истории. Стихотворения и стихотворные драмы Навроцкого («Патриарх Гермоген», «Ермак», «Патриарх Никон») написаны на сюжеты главным образом древнерусской истории, эпохи Смутного времени и раскола. Писал также комедии («Наследство») и произведения на темы недавней истории («Смерть Петра Великого», «Царь-Освободитель», «Царь-Миротворец»).
Стихи собраны в книгах «Картины минувшего» (Санкт-Петербург, 1881), «Светочи Русской земли» (Санкт-Петербург, 1896), «Сказания минувшего. Русские былины и предания в стихах» (кн. 1—3, Санкт-Петербург, 1896, 1899, 1902), «По Волге. Волжские былины и сказки в стихах» (Санкт-Петербург, 1903).
В стихотворной технике и подходе к историческому материалу признается эпигоном Л. А. Мея, А. Н. Майкова, А. К. Толстого (А. И. Рейтблат).
В творчестве Навроцкого выделяются стихотворение «Утёс Стеньки Разина» («Есть на Волге утёс…»; написано в 1864 году, опубликовано в 1870 году) и драматическая хроника «Стенька Разин» (1871). К стихотворению «Утёс Стеньки Разина» Навроцкий сам сочинил музыку и издал её в 1896 году вместе с текстом в качестве «музыкальной думы». «Стенька Разин» — первая пьеса Навроцкого («Вестник Европы», 1871). Оба произведения навеяны народными преданиями и песнями о вожде народного восстания Степане Разине, также книгой «Бунт Стеньки Разина» (1858) известного историка Н. И. Костомарова, которому посвящена пьеса.
Русские революционеры издали переделанную драму без указания автора под названием «Вольный атаман Степан Тимофеевич Разин» в Женеве в 1873 году. Издание заканчивалось стихотворением «Есть на Волге утёс». Два отрывка из драматической хроники вошли в революционный «Песенник» (Женева, 1873). Оба издания использовались в народнической пропаганде; см. Агитационная литература.
Стихотворение пользовалось огромной популярностью среди радикальной молодежи, было положено на музыку и, по словам писателя И. И. Ясинского, «имело значение русской марсельезы». Песня включалась в революционные песенники.
А. А. Навроцкий издал в Вильне книгу «О воинской дисциплине и средствах к ее охранению и надлежащему развитию» (1874), адресованную главным образом офицерам, и пьесу «Царевна Софья» (1874).
Годы службы в Вильне вызвали его интерес к истории Литвы. Стихотворная драма в пяти действиях «Крещение Литвы» (1874) опубликована в сентябре 1879 года в журнале «Русская речь». С исправлениями и дополнениями пьеса вошла в третий том сочинений Навроцкого (Петербург, 1900). Для интродукции, антрактов, отдельных эпизодов (мазурка, песня, шествие жрецов, погребальный гимн) и финала пьесы Навроцкий сочинил музыку.
С новыми поправками, дополнениями и нотами пьеса А. А. Навроцкого «Крещение Литвы. Эпизодическая драма в 5-ти действиях и 6-ти картинах, в стихах» увидела свет в Петербурге в 1902 году.
Действие драмы происходит в Вильне. В драме изображен переломный эпизод литовской истории — падение язычества и введение католической веры в 1387 году после брака великого князя литовского Ягайло и королевы польской Ядвиги. Пьеса предваряется кратким введением в историю Литвы с ссылками на труды по истории России, Литвы и Вильны русских и польских историков С. М. Соловьева, Т. Нарбутта, Ю. И. Крашевского и М. Балинского. В издании 1902 года перечень источников пополнили «История государства Российского» Н. М. Карамзина и «Белоруссия и Литва. Исторические судьбы Северо-Западного края» П. Н. Батюшкова.
Часть персонажей стихотворной драмы Навроцкого — реальные исторические деятели (Ягайло, Ядвига, архиепископ Бодзанта, польские вельможи из свиты Ядвиги), часть героев, главным образом литовцы, в частности, из окружения креве-кревейто Лиздейко (верховного жреца) — вымышлены. Характеры главных героев и исторический антураж отчасти заимствованы из романа «Поята, дочь Лездейки, или Литовцы в XIV веке» (1825) польского писателя Феликса Бернатовича, переведенного и на русский язык.
Драма в стихах «Иезуиты в Литве» (1876) изображает другой важный эпизод в истории Литвы — проникновение иезуитов и усиление их власти в правление Стефана Батория. Действие драмы также происходит в Вильне. Среди персонажей — люди разных национальностей, вероисповеданий, сословий. В драме происки иезуитов и укрепление позиций католицизма в последнюю четверть XVI века оценивается как сокрушительный удар по сложившемуся в Литве образу жизни с традиционной веротерпимостью. Король Стефан Баторий, понимая, какой ущерб наносит стране деятельность иезуитов, вынужден опираться на них в борьбе с своевольными вельможами.
Стихотворную драму «Крещение Литвы» на литовский язык перевёл католический священник, поэт, переводчик Мотеюс Густайтис. Перевод пьесы вместе с нотами и предисловием М. Густайтиса был издан на литовском языке в 1927 году в Каунасе.