11 ноября 1829 г. граф стал ротмистром, а спустя год (24 декабря 1830 г.) был переведён, также адъютантом, в распоряжение руководителя III отделения Собственной Его Императорского Величества канцелярии генерала А. Х. Бенкендорфа (к слову, получившего образование в С.-Петербургском Иезуитском пансионе). Очевидно, служба под началом шефа жандармов не удовлетворяла графа, и уже 21 января 1831 г. он был переведён адъютантом к фельдмаршалу И. И. Дибичу-Забалканскому, в том же году приняв участи в подавлении Польского восстания. За отличие в сражении Н. А. Протасов был награждён орденом св. Анны 2 степени (15 февраля 1831 г.), а за взятие Варшавы – орденом св. Станислава 2 степени (18 октября 1831 г.). В том же году, 7 июня, он получил придворное отличие – стал флигель-адъютантом Николая I, а 30 августа – чин гвардейского полковника.

На этом его военная служба фактически завершилась, в дальнейшем он служил «по гражданской части». Его карьера стремительно развивалась. 28 февраля 1834 г. графа, остававшегося флигель-адъютантом, назначили членом Главного правления училищ и Комитета устройства учебных заведений, а 10 марта 1834 г. – членом Главного управления цензуры. Уже через год, в возрасте 36 лет (11 апреля 1835 г.), Н. А. Протасов получил назначение исправляющим дела товарища министра народного просвещения[615]. По поводу состоявшегося назначения профессор С.-Петербургского университета А. В. Никитенко, в мае 1835 г. «вместе с прочими профессорами» представлявшийся новому товарищу министра, заметил, что это молодой человек «без физиономии». «У нас молодые люди, – полагал профессор, – раз напечатавшие где-нибудь в журнале свое имя, считают себя гениями; так же точно люди, надевшие военный мундир с густыми эполетами, считают себя государственными людьми, наравне с Меттернихами и Талейранами»[616].

Насколько было ошибочно мнение Никитенко о том, что граф Н. А. Протасов – человек «без физиономии», доказала последующая его деятельность в качестве обер-прокурора Св. Синода. Но и ранее он далеко не на всех производил впечатление человека «без физиономии». Показательные воспоминания о графе оставил профессор Н. Г. Устрялов, в николаевское царствование фактически ставший официальным историком, по учебникам которого обучалось несколько поколений русских студентов. На Святой неделе 1835 г., во вторник (Пасха тогда пришлась на 19 апреля, следовательно, речь шла о 21 апреля), «всё учёное и учебное сословие собралось у Чернышёва моста в огромной зале министра [народного просвещения] для поздравления в полных мундирах», – вспоминал Устрялов. На встречу с ними вышел министр граф С. С. Уваров, «с товарищем своим, гусарским полковником, обер-прокурором Синода графом Протасовым», христосовался со многими, разговаривал (по-русски, по-французски, по-немецки) «обо всех учёных предметах». Когда приём завершился и все стали уходить, курьер пригласил Устрялова к министру. Граф Уваров, рядом с которым находился Протасов, сказал профессору, что они согласны послушать его сочинение, назначив для этого особый день. В пятницу, 25 апреля 1835 г., Устрялов прибыл в кабинет к министру, куда, некоторое время спустя, стуча саблей, быстро вошёл граф Протасов.