Родился 24 марта 1804 г. в семье крепостных крестьян графа Шереметева в с. Удеровка Бирюченского уезда Воронежской губернии (ныне Алексеевский район Белгородской области). При содействии К. Ф. Рылеева и его друзей в 1924 г. получил «вольную» и поступил на философско-юридический факультет Петербургского университета. В 1837 г. защитил диссертацию «О творящей силе в поэзии, или о поэтическом гении».

 
Служил в канцелярии попечителя Санкт-Петербургского учебного округа, читал курс политической экономии в Санкт-Петербургском университете; преподавал в Екатерининском институте и Александровском училище. 

В своем труде «Опыт истории русской литературы» попытался создать периодизацию русской литературы. А. В. Никитенко служил цензором Санкт-Петербургского цензурного комитета (1833–1848 годы). 

Строго следуя положениям Цензурного устава, А.В. Никитенко в своей деятельности стремился оградить права писателей от произвола цензурных чиновников, видел в цензоре посредника между писателем и правительством. Был чрезвычайно осторожен в своей цензорской практике, однако пропустил в печать «Мёртвые души» Н.В. Гоголя (1842 год), исключив «Повесть о капитане Копейкине», в 1847 году помог Д.В. Григоровичу в «продвижении» через цензуру повести «Антон-Горемыка», в 1856 году содействовал выходу «Стихотворений» Н.А. Некрасова. 

А.В. Никитенко был цензором произведений А. С. Пушкина, Н.В. Гоголя, Л.Н. Толстого, М. Ю. Лермонтова, И. С. Тургенева. В 1847–1848 гг. он являлся редактором журнала «Современник».
Посмертный «Дневник» А.В. Никитенко содержит исключительно редкие, наполненные большим фактическим материалом записи по истории русской общественной мысли, литературы и искусства 1820-1870-х гг. 

А.В. Никитенко был членом правления Общества посещения бедных (с 1850 года), в 1870-х годах — членом Славянского комитета, Общества любителей христианского просвещения, ряда благотворительных обществ.