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