Лишённый по неродовитости своей возможности посещать Английский клуб (где, как говорили, можно было услышать живую британскую речь), Костенко стал завсегдатаем кронштадского порта и петербургских кабаков, в которых собирались иностранные моряки. Там он освоил язык притонов и подворотен, научившись даже различать некоторые диалекты. Впрочем, само по себе знание английского больших дивидендов ему не принесло. Переместившись благодаря своей энергии на два чиновничьих класса, Костенко на некоторое время остановился в служебном росте, ибо все хлебные места были прочно заняты ветеранами Венского конгресса, которые твёрдо были намерены досидеть на них до конца.
И тут как нельзя кстати разразилась Крымская война. Катастрофичная для России, она явилась истинным подарком судьбы Костенко. Позиции прежних вершителей европейской политики ослабли, на смену им пришло новое поколение дипломатов, ведомых князем Горчаковым. Сразу же вскрылись неблаговидные делишки, которые творились за спиной, а может, и с ведома ушедшего канцлера. Проверки, затеянные новым министром, вскрыли многочисленные злоупотребления по хозяйственной части, а также повальное взяточничество, шедшее не раз во вред российским интересам. Среди прочего, были выявлены случаи прямой измены, когда чиновники министерства покрывали аферы фабричных ловкачей, сбывавших ценные материалы англичанам, французам и туркам. Разбирая один из таких случаев, Костенко представил бумаги, из которых со всей очевидностью следовало, что продавать врагам оружие не брезговало даже знаменитое семейство Нобелей. Их предприятие было отстранено от военных поставок, а карьера Костенко опять пошла в гору. К началу польского мятежа он уже ходил в чине надворного советника и состоял в штате статс-секретаря по европейским делам.
В министерстве он был на хорошем счету, а потому, когда возник вопрос о дипломатическом представителе в американскую экспедицию, долго выбирать не пришлось. Великолепное знание английского и сообразительность делали Костенко кандидатурой номер один. Немаловажное значение имели и навыки кулачного боя, приобретённые им в припортовых забегаловках. Одно время Костенко даже брал уроки бокса у портсмутского шкипера, но далеко в этом не продвинулся – помешали скудные финансы и недостаток времени. Впрочем, пару хороших ударов он освоил и при случае мог отбиться от парочки подвыпивших драчунов.