В 1823 году Кошелев поступил на службу в Московский архив Коллегии иностранных дел – хранилище дипломатических документов допетровской эпохи и начала петровского царствования. При архиве уже состояли представители золотой молодежи того времени: Одоевский, Веневитинов, С.П. Шевырев, через которых Кошелев познакомился с будущими декабристами Е.П. Оболенским, И.И. Пущиным, К.Ф. Рылеевым, М.А. Фонвизиным. Служба не была обременительной, и начальник архива А.Ф. Малиновский, чтобы как-то занять «архивных юношей», заставлял их описывать по годам дипломатические отношения России с тем или иным государством. В свободное время юноши упражнялись не только в любомудрии и литературной полемике, но также совершенствовали навыки верховой езды и фехтования: казалось, что эти умения понадобятся в случае «решительных действий». В преддверии событий декабря 1825 года «любомудры» заняли более радикальные позиции, а Кошелев на собраниях, проходивших у его троюродного брата М.М. Нарышкина, даже высказывался о «необходимости произвести в России перемену правления». Предчувствие революционных потрясений, атмосфера конспиративности, ассоциации с 1789 годом во Франции даже несколько охладили интерес «любомудров» к немецкой философии, актуализировав идеи французских политических мыслителей XVIII века.
Восстание на Сенатской площади взбудоражило Кошелева и его товарищей: каждый день ожидали новых известий, ежедневно тренировались в манеже, готовились к любому развитию событий, в том числе к аресту. Правда, до «аннибаловой клятвы» дело не дошло. Воодушевление вскоре сменилось разочарованием и укрепило в них уверенность в неприемлемости революционного пути, в необходимости просвещения и нравственного самосовершенствования.
Такова была эволюция мировоззрения молодого Кошелева: от космополитизма домашней обстановки и культуры классицизма – через немецкий романтизм с кратковременным вкраплением якобинского радикализма – к идее национальной самобытности, религиозности, народности. В 1827 году у постели умирающего Веневитинова он познакомился с А.С. Хомяковым и вскоре окончательно присоединился к славянофилам.
В 1826 году Кошелев получает назначение в Петербург в Канцелярию министра иностранных дел К.В. Нессельроде, где готовит обзоры иностранной прессы о России для императора Николая I. Очень пригодилось не только владение языками, но и полученное в Московском архиве Министерства иностранных дел знание истории взаимоотношений России с другими государствами. Кошелев добросовестно исполняет свои обязанности, успешно продвигаясь по службе. В 1829 году его переводят в Департамент духовных дел иностранных исповеданий для разработки «Общего устава для лютеранских церквей в Империи».
Кошелев живет у своего дяди Р.А. Кошелева – известного в то время мистика, близкого к окружению императора, дом которого, как магнит, притягивал самую разную публику. Столичная жизнь целиком захватила молодого аристократа: он принят в модных салонах, посещает балы, театры; ширится круг знакомств, властительницы его сердца сменяют одна другую. Наконец он влюбился – страстно и безответно. Предложение, сделанное им А.О. Россет (в замужестве она более известна как Смирнова-Россет), было отвергнуто, и кто знает, чем бы этот неудачный роман закончился, если бы в 1831 году не «подвернулось» (не без дядиной протекции) назначение в качестве атташе российского посольства в Лондоне. Кошелев уехал, поставив крест на светских развлечениях и своей несчастной любви.
В 1831 году он в свите А.Ф. Орлова участвовал в подписании Лондонского договора об учреждении Бельгийского королевства. К этому времени относится один колоритный эпизод его биографии.
А.Ф. Орлов был практически всесилен: любимец императора, герой Отечественной войны 1812 года, государственный сановник высшего ранга. Перед ним лебезили, заискивали; ему не смели перечить. Он вел себя соответственно – бесцеремонно, фамильярно, свысока. Кошелев с неприязнью наблюдал подобные сцены: служить он готов был честно, но прислуживаться ему было тошно.
Однажды Орлов, обращаясь к свитским на «ты», спрашивал их поочередно, поедут ли они с ним на охоту. «Эдак он и нам „тыкнет“, – заметил Кошелев одному своему товарищу, и в тот же миг Орлов, остановив на нем взгляд, в упор спросил: – „А ты?“ Пауза была недолгой. „С тобой я везде поеду“, – не дрогнув, отвечал Кошелев».