В 1861 году Леонтьев женился на дочери феодосийского торговца Елизавете Политовой, с которой познакомился еще в 1855 году в Крыму. Так случилось, что его попутчиком в поездке в Феодосию оказался российский консул на острове Сир Дубницкий. Его живописные рассказы о Востоке вызвали у Константина Николаевича желание попробовать себя на дипломатическом поприще. Это желание было еще больше подогрето встречей со старым знакомым по Калуге Хитрово, назначенным первым российским консулом в Битоли. В 1862 году Леонтьев вернулся в Петербург и в феврале 1863 года был зачислен в Азиатский департамент МИД.
Спустя 8 месяцев его назначают секретарем и драгоманом консульства на Крите. Молодой дипломат хорошо изучил местные обычаи, традиции, разобрался в политической ситуации, много и неформально общался с населением. Однако, не пробыв на Крите и года, он был отозван в Константинополь после ссоры с французским консулом, которого ударил за то, что тот плохо отозвался о России. Впоследствии поведение Леонтьева получило одобрение вице-канцлера Горчакова.
27 августа 1864 г. Леонтьев был назначен секретарем и драгоманом консульства в Адрианополе, где с небольшими перерывами пробыл до апреля 1867 года, а в 1865 году был награжден орденом Св. Анны 3-й степени.
Адрианополь Леонтьеву не понравился. Этот "смрадный город" не пришелся ему по душе, хотя "и в нем много поэзии". А поэзия его прежде всего "заключалась в простом народе, в турецких кварталах, в мечетях, в кладбищах, в банях, в хорошеньких девочках предместий..." Современники так характеризовали Леонтьева: "Он был странно уверен, что от радости люди забываются и забывают о Боге. Потому не любил он, чтобы кто-нибудь радовался. Он точно не знал и не понимал, что "любовь изгоняет страх", - нет, он не хотел, чтобы любовь изгнала страх. Для Леонтьева христианство было только якорем личного спасения, он сам старался сжать всю свою религиозную психологию в рамки "трансцендентного эгоизма..."
Замараев отмечал: "У него было сильно развитое эстетическое чувство. Когда он, например, слушал пение, то весьма редко глядел на поющего: для этого нужно было иметь певцу особенно счастливую, изящную наружность, которая бы не портила впечатления. Константин Николаевич не любил также, когда кто-нибудь услужливо подавал ему зажженную спичку, чтобы закурить папироску: из опасения увидать не совсем чистые ногти он всегда спешил взять спичку в свои пальцы..."
20 октября 1865 г. консул в Адрианополе Золотарев направляет в МИД его "Записку о необходимости литературного влияния во Фракии". В ней Леонтьев проводит мысль о том, что в борьбе России с Западом за влияние на славян "необходимо наряду с политикой и религией использовать литературу и искусство, чтобы греки и славяне видели в России своеобразный государственно-национальный организм". Кроме того, Россия должна оказывать культурное воздействие на народы Балкан через организацию и развитие там школьного дела.
Будучи неудовлетворен службой в Адрианополе и испытывая на занимаемой им должности недостаток в средствах, Леонтьев начал хлопотать о переводе на другое место. 15 апреля 1867 г. он получает назначение вице-консулом в Тульчу с производством в надворные советники, а спустя год награждается орденом Св. Станислава. "Я здесь точно русский помещик. Сижу с утра в чистом белье, усы подкручены, лицо вымыто душистым снадобьем, туфли новые, комната простая, но хорошая, кухарка русская, труд, так сказать, на поприще отчизны", - напишет он в одном из писем.
Тихомиров напишет впоследствии: "До тех пор не признаваемый, отрицаемый и более всего игнорируемый родной страной, он теперь почувствовал как будто некоторое признание. Это его утешало и окрыляло надеждами; он начинал думать, что в России есть еще над чем работать, и планы работ начинали роиться в его голове. Вообще, ему дано было провести конец жизни в относительно светлом настроении. Он мог думать, что он не изгой в своей родине, а первая ласточка той весны, которая изукрасит своими свежими цветами Россию, совсем было посеревшую в пыли своего национального самоотречения, псевдоевропеизма".
Весной 1872 года Леонтьев напишет свою знаменитую "Записку об Афонской горе и об отношениях ее к России". "Мы постоянно встречаем в этих великорусских выходцах людей, любящих нас, и главное, людей, которым можно верить". Работая в Тульче, Леонтьев опять испытывает недостаток в деньгах и начинает ходатайствовать о своем повышении. 7 января 1869 г. его назначают консулом в Янину. Но вскоре ему стало тесно в затерянном в горах маленьком, тихом городке, и он обратился к своему непосредственному начальству, послу в Константинополе Игнатьеву, с просьбой перевести его в другое место, желательно на Дунай.