7 июня 1859 г. пароходо-корвет «Америка» под флагом генерал-губернатора Восточной Сибири взял курс на Хакодате. К 15 июня туда же подошли корветы «Гридень» и Рында», а также фрегат «Аскольд», которому предстояло увезти из Хакодате в Россию японские подарки. Так что у Муравьева-Амурского собралась целая эскадра. Начальником штаба назначили командира корвета «Аскольд» И. С. Унковского. Муравьев-Амурский пересел с «Америки» на «Аскольд» и в сопровождении эскадры отправился в Токио на переговоры по разграничению Сахалина, которые имели стратегическое значение для России.

1 августа 1859 г. корветы «Рында» и «Гридень» вошли в Токийский залив. На рейде Канагавы уже стояли корвет «Новик» и пароходо-корвет «Америка». Канагаву открыли для иностранцев после гибели фрегата «Диана» у берегов Симоды. Тогда европейцы настояли, чтобы им предоставили другой, более безопасный для мореплавания порт. Чтобы отделить чужеземцев от японцев, им выделили место в двух верстах от города, названное Юка-амой (Йокогамой), где имелась хорошая и глубокая бухта. Там быстро соорудили пристани, просторные склады и открыли лавки. Были даже построены дома для иностранных консулов, но они предпочли жить в Канагаве.

«Половина Йокогамы, — писал лейтенант А. А. Корнилов с клипера «Джигит», — занята большими деревянными, по обыкновению очень отчетливо отделанными зданиями, назначенными под склады товаров, подлавки и жилища иностранцев. В 2-х, 3-х лавках этих нам мало пришлось купить вещей нам нужных; они наполнены большей частью галантерейными вещами, ружьями, пистолетами, шарманками и другими мелочами, которых нет у японцев. […] На берегу у длинных, каменных пристаней выстроено большое одноэтажное здание таможни. Внутри здания огромный двор, насыпанный крупным щебнем; для какой цели, право, не знаю, разве для того, чтобы иностранцы реже туда ходили. Боковые ниши здания назначены, кажется, для складов, в задней же или главной части помещается контора. Тут мы меняли наше серебро на японское, тут же находили, в случае надобности, переводчиков, чиновников и даже самого Канагавского губернатора, который, впрочем, принимает лично далеко не всех, имеющих в этом нужду, а чаще извиняется нездоровьем и высылает вместо себя вице-губернатора или чиновников, смотря по значимости пришедшего лица».

Когда 4 августа фрегат «Аскольд» с Муравьевым-Амурским на борту пришел в Йокогаму, на рейде стояло восемь русских паровых кораблей, что представляло серьезную силу. На следующий день эскадра перешла в бухту Токио. «Вид Иедо с рейда очень красив, — отмечал Корнилов. — Раскинутый по холмам, он не может похвастаться ни одним высоким выдающимся зданием, но зато щедро рассыпанная зелень вознаграждает этот оригинальный, для столицы с двумя миллионами, недостаток. […] Весь город состоит из кривых узких улиц, обустроенных небольшими, тесно друг к другу прилегающими, иногда двухэтажными с лавкою внизу домишками или высокими деревянными стенами, окружающими княжеские дома. В первом случае улицы кишат нагим народом, а во втором пусты и безмолвны. Иногда попадаются храмы, но из них только один замечателен по массивности громадной крыши с резьбой и высокой колокольней.

Княжеские дома, занимающие большей частью целые кварталы, встречаются беспрепятственно, но в них кроме высоких стен и резных массивных ворот со страшными запорами ничего не видно. Даже дворец Тайкуна, несколько дней бывший целью почти всех наших прогулок, далеко не удовлетворил нашим ожиданиям. Довольно большая возвышенная местность, обкопанная широким рвом и обнесенная стеной, из-за которой везде проглядывали деревья и кое-где беседки, — вот и все, что мы можем сказать о дворце Тайкуна. Его таинственная неприступность, холм, на котором он выстроен, и зелень, пожалуй, иногда расшевелят воображение; но стоит только вспомнить, что это дворец властителя Японии, как фантазия оставит вас и вам останется лишь одна японская жизнь, так мало вызывающая сочувствие европейца. Как ни старайтесь обставить мысленно внутренность этих дворцов, кроме разрисованных бумажных ширм вместо стен и чистых циновок на полу ничего не придумаете. Единственная сторона, с которой мне понравился город, это бесчисленные парки и сады, частные и публичные, между которыми нам показали даже ботанический».

Организацией переговоров в Токио занимался Гошкевич. 8 августа 1859 г. уполномоченные императора Эндо Тадзима-ноками и Сакаи Укёноскэ посетили графа на борту фрегата, а на 10 августа был назначен съезд на берег. Он был обставлен очень торжественно. При переходе Муравьева-Амурского с фрегата «Аскольд» на «Америку», которая могла поближе подойти к берегу, раздался салют, и все матросы были посланы на реи. Чуть позже по бухте засновали шлюпки, заполненные офицерами в парадной одежде. У самой пристани графа встречали японские чиновники, а также сборный батальон, составленный из экипажей всей эскадры. Вид трехсот лихих матросов, гардемаринов и юнкеров, блестящие мундиры и знамена должны были произвести впечатление на японский народ. К сожалению, людей на берегу не было, так как полицейские запретили горожанам появляться там во время церемонии. Так что красочным представлением наслаждались сами участники. В храме гостей ждал торжественный обед, составленный из блюд японской кухни.

Русские моряки с удовольствием воспользовались возможностью осмотреть незнакомый город, в который не ступала нога иностранца. На их взгляд, народ на улицах почти ничем не отличался от жителей Хакодате или Нагасаки. Простой люд ходил почти раздетым, не блистали богатством и одежды лавочников. Кто выделялся среди толпы, так это чиновники, которые выглядели поважнее, чем в других городах, которые посещали русские. Да и свиты у знатных людей были значительно многочисленнее. Лавки были побогаче канагавских, но не везде соглашались продать товар иностранцам.

Русских моряков очаровали красота и утонченность японских женщин, хотя они и недоумевали по поводу некоторых японских обычаев. «Что касается женщин, то мы, разумеется, других случаев, как видеть их на улице, в лавках или гостиницах, не имели; а в этих местах, с прибавкой и храмов, показываются только женщины низшего класса, да и то сравнительно с мужчинами не в большом количестве. Между ними часто попадаются довольно хорошенькие, но, увы, то же злодейское обыкновение, что и в Хакодате, покрывать белилами и другими разноцветными мастиками лицо и шею невольно напомнит поблекшую, но все-таки играющую первые роли актрису провинциального театра».

В свою очередь японские жители тоже во все глаза глядели на чужеземцев. В Японии тогда существовало немало противников открытия страны, особенно среди чиновничества, поэтому прогулки нередко были сопряжены если не с опасностью для жизни, то во всяком случае с некоторыми неудобствами. Смех и крики зевак постоянно сопровождали русских во время их экскурсий по городу. Порой гостей встречали и камнями: кто-то маленькими, а кто-то и более увесистыми. Увы, узкие японские улицы не позволяли избежать неприятных встреч. Иногда в конце прогулки русские напоминали зайцев, которых гнали собаками.