В течение первого года работы консульства одной из основных проблем было строительство консульского здания. В инструкции, выданной Гошкевичу, отмечалось: «По прибытии в Хакодате Вы составите, согласно с Высочайше одобренным предначертанием, проект учреждения в сем городе школы и больницы и примете необходимые к исполнению его предварительные меры, вплоть до утверждения его установленным порядком. Участок, который на основании трактата (имеется в виду российско-японский договор, заключенный в Симоде в 1855 г. — А. Х.) будет отведен под Консульский дом, должен находиться в городской черте, согласно с изустным обещанием, данным капитану Посьету Японскими уполномоченными, и соединять нужные удобства с достаточной обширностью для возведения дома со службами, собственно для Консульства, магазинов для складки товаров и каменного угля, а также помещения для приезжих». Скорее всего, в столице уже были наслышаны об особенностях японского характера, и в инструкции Гошкевичу советовали не сообщать раньше времени японским властям ни числа, ни рода предполагаемых построек.
Вопрос с выделением участка для консульства долго не решался. Ни письма консула губернатору, ни личные визиты не могли ускорить дела. Японцы добросовестно раскладывали на полу огромную разрисованную от руки карту Хакодате, но стоило русским показать место в центре города, рядом с домом губернатора, как разыгрывалась одна и та же сцена. Японцы делали вид, что не понимают гостей, и предлагали им расположиться за городской чертой, в местечке, удаленном от города на 3 км. Было очевидно желание японцев поселить всех иностранных гостей рядом друг с другом, чтобы облегчить контроль над их передвижениями.
«Ваши усилия заставить всех иностранцев жить в одном месте бесполезны, — возражал Гошкевич. — Этот способ, который вы применяли в отношении голландцев в Нагасаки, уже невозможен». При этом русский консул показал на карте участки, не занятые постройками, и предложил рассмотреть их на месте. Губернатор с большой неохотой согласился и выделил офицеров, чтобы сопроводить русских. Но дело так и не получило завершения. Сначала губернатор захотел сам осмотреть эти участки, потом заявил, что надо запросить разрешение у столицы Эдо, на что может уйти целый год. После долгих переговоров и раздумий японцы все же решились выделить для иностранцев участок О-мачи (O-machi, ныне Nakahamamachi), который тогда граничил с городом.
О том, как строилось консульство, известно со слов литератора С. В. Максимова, побывавшего в Хакодате и узнавшего обо всем от Гошкевича: «Понадобилось русскому консулу место для дома, и состоялся приказ Сёгуна не пускать пришельцев селиться в среде города, не отводить им мест удобных в центрах населения. Хакодатское начальство не задумывалось. Была у них на горе, за городом, великолепная кипарисовая роща. Место это отлично согласовывалось со смыслом предписания из Иедо и видами высшего правительства, но представляло большие неудобства и трудности в том отношении, что гора была слишком отлога, слишком крута для того, чтобы можно было применить к ней русское здание, задуманное по нашему обыкновению в широких размерах. Как быть? Хакодатский губернатор согнал огромные массы рабочих, в короткое время немногих месяцев муравьи эти, не знающие устали, вырезали из горы громадный кусок (в несколько десятков сажень длины и ширины), как раз достаточный для того, чтобы иметь вид огромного плаца и поместить консульский дом со всеми службами, даже с церковью и домами секретаря и доктора». Когда понадобился участок для Британского консульства, процедура повторилось. Вынутую землю использовали для того, чтобы обустроить новую террасу.
Назимов произвел разбивку места под здание консульства и составил проект двухэтажного дома для консула, одноэтажного для врача, а также больницы и бани. Для строительства можно было нанять только японских рабочих, привыкших к японскому стилю архитектуры. Поэтому решено было внутреннюю обстановку сделать так, как в японских домах, а внешний вид — по-европейски. По разработанному плану были сооружены двухэтажное здание самого консульства и четыре одноэтажные постройки для проживания русских семей. Строительство шло быстрыми темпами. Губернатор Хакодате лично следил за его ходом и выполнял все просьбы русских. Правда, Назимов замечал, что за все постройки японцы «сравнительно берут дорого и делают непрочно, штукатурка обвалилась».
В апреле 1860 г. сотрудники Российского консульства переехали в новые здания. Они были очень небольшими, но все же отличались от японского жилья в лучшую сторону. Особенно важным русские считали, что можно будет печь хлеб и сушить сухари: некоторые никак не могли привыкнуть к японской еде. «Вообще Хакодате, — писал Махов, — мало-помалу начинает украшаться новыми домами, принадлежащими как иностранцам, так и японцам; дом нашего консула уже совершенно готов, и можно смело сказать, что он и наша церковь — лучшие здания в городе».