На первый взгляд, военно-морская карьера не имела прямого отношения к дипломатии, но характер Путятина подходил к этой роли как нельзя лучше: он мог, когда нужно, быть покладистым, оставаясь жестким и требовательным в принципиальных вопросах. Не случайно Министерство иностранных дел выбрало его для выполнения разных поручений в Китае и Японии, куда офицеру предстояло отправиться в 1853 г. из Англии на фрегате «Паллада». Некогда краса и гордость Российского военно-морского флота, этот корабль по-хорошему ни на что, кроме местных плаваний, уже не был пригоден: медные листы обшивки во многих местах были оторваны, дно обросло ракушками, но, исходя из каких-то соображений, Морское ведомство выделило послу именно его.
Перед дальним походом в Восточный океан «Паллада» в октябре 1852 г. зашла на ремонт в Англию, где ее поставили в портсмутский док. Пока на судне шли работы, Путятин сделал, как окажется впоследствии, весьма важное приобретение для Дальнего Востока. Он купил в Бристоле винтовую шхуну и назвал ее «Востоком» в честь другого славного русского судна. Забегая вперед, надо сказать, что новый «Восток» оказался достойным преемником корабля, открывшего Антарктиду, став не только первой железной шхуной, плававшей в дальневосточных морях, но и прославившись своими географическими открытиями. Командиром шхуны Путятин назначил лейтенанта Воина Андреевича Римского-Корсакова. К началу 1853 г. «Паллада» вышла из дока, и 6 января оба судна снялись в дальний путь.
Хотя ремонт частично восстановил былые мореходные качества «Паллады», дальний переход подтвердил опасения Путятина. Он писал в своем рапорте: «Слабость и неблагонадежность нашего старого фрегата к продолжительному плаванию подтвердилась неопровержимым образом: он потек всеми палубами, и сверх того обнаружилось движение в креплениях надводной части». Течь была настолько сильной, что вода проникала всюду, и две помпы с трудом с ней справлялись. Это очень напутало И. А. Гончарова, секретаря Путятина, который даже хотел вернуться домой.
В этом историческом плавании у Путятина были замечательные спутники. Фрегатом «Паллада» командовал капитан 2-го ранга Иван Семенович Унковский. Офицеры отмечали, что этот лихой капитан, прослуживший семь лет адъютантом знаменитого адмирала М. П. Лазарева, с которым совершил три кругосветных плавания, обладал благородными манерами и добрым характером. Большую роль в переговорах с Японией сыграл переводчик Иосиф (Осип) Антонович Гошкевич. В то время в России не было ни одного японоведа, но Гошкевич, окончивший Петербургскую духовную академию, одиннадцать лет прослужил в Российской духовной миссии в Пекине и отлично знал китайский язык. После возвращения из Китая в Санкт-Петербург его назначили драгоманом при Азиатском департаменте Министерства иностранных дел. Когда летом 1852 г. вице-адмирал Путятин обратился туда с просьбой откомандировать в его дипломатическую экспедицию двух переводчиков, выбор пал на Гошкевича, и он оказался безошибочным.
Вечером 9 августа 1853 г. «Паллада» подошла к нагасакскому рейду. Уже темнело, никто на фрегате рейда не знал, поэтому решили подождать до утра в дрейфе. Моряки толпились на палубе, пытаясь рассмотреть берега.
Японцы, уже осведомленные о цели прихода русской эскадры, сразу же поднялись на борт фрегата. Общение свелось к выполнению формальностей. Разговора не получилось. Офицеры заметили, что японцы уходили от ответов на вопросы даже самого незначительного свойства и старались не давать никакой информации.
Русских очень удивило, что они обошли молчанием приход в Японию командора Перри. «Вида не показывают, что американцы были у них в Едо, — писал в дневнике Гончаров. — Они думают, что мы и не знаем об этом; что вообще в Европе, как у них, можно утаить, что, например, целая эскадра идет куда-нибудь или что одно государство может не знать, что другое воюет с третьим». Но и явную неправду японцы тоже не говорили: чтобы не потерять лицо, как поняли моряки.
Большинство просьб русских также осталось без ответа. При этом японцы ссылались на вышестоящее начальство: якобы только оно могло решить тот или иной вопрос. Но свежую провизию пообещали доставить без промедления. И действительно, во время стоянки в Нагасаки моряки не нуждались в продовольствии, оно доставлялось на «Палладу» и «Восток» в достаточном количестве: с берега через голландцев или же транспортом «Князь Ментиков» из Шанхая, до которого от Нагасаки было всего трое суток плавания. Погода держалась отличная, здоровье офицеров и матросов было удовлетворительным. На обоих русских судах ежедневно проводились учения: то парусные, то артиллерийские. 6 сентября 1853 г. во время учений произошел несчастный случай: матрос 23-го экипажа Борисов при поднятии парусов упал по собственной неосторожности с фор-салинга на палубу и при падении получил переломы костей с признаками сотрясения мозга, отчего через несколько часов умер.