20 февраля 1861 года «Посадник» из Хакодате вышел курсом на Цусиму и уже 1 марта бросил якорь вблизи деревни Осаки в западной части бухты Татамура (ныне залив Асо). Главой княжества Цусима в ту пору был Мунэ Ёсиери. По прибытии в Цусиму Бирилев заявил:
— Я хочу вручить главе княжества послание русского императора о готовящемся нападение англичан и обязательно встретиться с ним!
Мунэ Ёсиери с русским офицеров встретился, но все ограничилось чайной церемонией. Помимо этого князь отправил Бирилеву 20 литров саке и 20 куриц. Бирилев в качестве ответного дара передал ружье, бинокль и несколько бутылок вина. Князю подарки понравились, и отношения наладились.
О приходе русских Мунэ Ёсиери сообщил правительству бакуфу, но никакого ответа не получил. Престарелый Андо Нобумаса (глава тогдашнего японского правительства) был застигнут сообщением врасплох и откровенно не знал, что делать дальше.
Затем Бирилев добился разрешения Мунэ Ёсиери на обследование бухты Имоскака, куда корвет перешел 2 апреля. На следующий день команда сошла на берег, где была поставлена палатка и на флагштоке поднят русский флаг. Русские офицеры во главе с Бирилевым осмотрели берег и выбрали место, удобное для постройки склада и лазарета, а также ремонта корвета, поскольку необходимо было заменить фок‑мачту и сделать понтоны для осмотра кормовой части корабля и дейдвудной трубы. Японские чиновники выделили в помощь русским матросам пятнадцать плотников и снабдили команду продовольствием. При входе с запада в бухту Татамура на скалистом островке Уси русские моряки установили сигнальный пост.
Лихачев дважды – в марте на клипере «Опричник» и в апреле на фрегате «Светлана» – посетил Цусиму и остался доволен действиями командира «Посадника». Бирилев в рапорте Лихачеву отметил дружелюбное отношение местного населения к русским. При рубке леса японцы указывали на лучшие деревья и помогали доставлять бревна. Очень им понравилась русская песня «Дубинушка». В начале апреля русские моряки и японские плотники приступили к строительству зданий морской станции. Предстояло построить коттедж для командира, больницы, бани, шлюпочные и угольные сараи и другие постройки. Во время отлива «заложили пристань и 20 футов ширины».
Бирилев для начала подарил Мунэ Ёсиери пару малокалиберных пушек из вооружения гребных судов. Для обучения японских мальчиков русскому языку на Цусиме была организована небольшая школа. Бирилев рапортовал, что «дружба царствовала во всей силе».
Однако, как явствует из японских источников, все наладилось не сразу. 12 апреля, когда русские матросы начали высадку на берег, жители деревни по инициативе крестьянина Ясугоро попытались воспрепятствовать этому. Ясугоро был убит, двух японцев русские взяли в плен, а остальные жители деревни разбежались. Волнение охватило весь остров, сложилась напряженная ситуация. Это событие встревожило Мунэ Ёсиери, но он успокаивал жителей, говоря, что «это дело государственное и следует обратиться по этому поводу к правительству бакуфу, мы направим туда гонца. Поскольку решается судьба дома Мунэ, прошу проявить преданность, чтобы не запятнать имени дома».
Затем все само собой успокоилось и отношения стали на самом деле вполне дружескими. Тем временем «Посадник» разоружился, сняли часть рангоута, и приступили к ремонту корабля. Часть команды занялась подсобным хозяйством и развела огород. Описная партия под руководством старшего штурмана корвета подпоручика Чуркина занялась промером глубин. Карты островов Цусима, составленные офицерами «Посадника», впоследствии были изданы Гидрографическим департаментом Морского министерства.
В мае в Цусиму приехал, наконец, уполномоченный правительства бакуфу Огури Тадамаса. Между ним и Бирилевым состоялась встреча. Огури вежливо потребовал ухода русских, но Бирилев отклонил требование и заявил, что «без приказа начальства из Цусимы ни за что не уйдет». Огури, напрасно прождав тринадцать дней, покинул Цусиму. Во время беседы Огури вручил Бирилеву документ, разрешающий встречу с главой княжества.
В конце концов, Бирилев сумел договориться с главным советником князя Мураока Ооми и губернатором острова Нии Моготииро. Участники совещания подготовили проект, где, между прочим, говорилось: «Князь Тсусимский вполне желает принять покровительство России во всех отношениях, во исполнение чего если Русское Правительство признает нужным держать здесь суда, то мы согласны охотно на это, и место от Хироуры до Имосаки включительно и по указанную черту отдать в распоряжение русских судов и под защиту их всю бухту Татамура, то есть от Усисима до Обунокоси. С другими нациями никакого дела иметь не будем. Мы просим Русское Правительство снабдить нас сколько будет можно новейшими огнестрельными оружиями, а также и просим русских обучать наших молодых офицеров новейшему военному делу… просим русских не нарушать наших древних обычаев и не стараться вскоренять их веру… Но все это мы можем выполнить только тогда, если не будет к тому препятствий со стороны нашего Правительства в Эдо».