В биографии графа, составленной неизвестным лицом вскоре после 1855 г., сообщалось, что, обладая сангвиническим темпераментом, в детстве он имел кроткий и тихий характер, а в отрочестве – «проворный» и «любознательный». Первые годы его жизни связаны с Москвой и с подмосковным имением Горюшкино, располагавшемся в Дмитровском уезде. «Воспитан был дома в примерном благочестии, – указывал неизвестный биограф. – Все праздничные и воскресные дни и повечерии оных слушал Божественную литургию, чему способствовала домовая в том имении церковь, в которой за всенощным бдением постоянно почти читал шестопсалмие и нередко каноны и другие чтения». В учебные дни обучение всегда начиналось «по древнему обычаю: с Бога начало было всегда чтением вслух поочерёдно с товарищем учения его Андреем Дм[итриевичем] Бороздиным[609] главы из Св. Евангелия или Библии». Русский язык и Закон Божий преподавал ему московский священник Николай Краснопольский, тогда же изучал и английский язык, «которым владел свободно»[610].

Для изучения латинского и французского языков, а также «прочих предметов» матерью графа был приглашён домашний наставник эмигрант Прадель, «пользовавшийся большой известностью и уважением в Москве до 1812 года и после»[611]. Таким образом, можно утверждать, что образование Н. А. Протасов получал в Москве, а не в Петербургском Иезуитском пансионе, как об этом говорили некоторые современники, а вслед за ними и историки[612]. Значительное влияние на его воспитание оказала мать, которую называли женщиной замечательной по своей религиозности, благоразумию и основательности, к тому же пользовавшейся уважением при Дворе[613]. В первый раз Н. А. Протасов выехал за границу с матерью в 1816 г., посетив Германию, Францию и Англию. Осенью 1817 г. он вернулся в Москву, где в то время находился Двор и гвардия. Там он поступил на службу в лейб-гвардии Гусарский полк юнкером, а 26 августа 1818 г., по высочайшему повелению и «в утешение родительницы», был произведён в офицеры[614].

17 апреля 1819 г. граф Н. А. Протасов был назначен адъютантом к герою Отечественной войны 1812 г. генералу И. В. Васильчикову, командовавшему тогда отдельным гвардейским корпусом. Будучи адъютантом, 7 июня 1822 г. получил чин поручика, а через три с половиной года (28 января 1826 г.) – чин штаб-ротмистра. В 1828 г., в ходе Русско-турецкой войны, генерал Васильчиков сопровождал Николая I в поездке в действующую армию, участвовал в военном совете, принявшем решение о Забалканском походе русских войск. Протасов в то время находился при генерале. За кампанию 1828 г. получил орден св. Владимира 4 степени (9 февраля 1829 г.).