Экспедиция отправилась на трёх нартах, и три спутника были у лейтенанта Бошняка в этом далёком походе: Семён Парфентьев, Иван Мосеев, Кир Белохвостов. Невельской помог им собраться в Николаевском и проводил в путь 15 февраля.

По дороге заехали в нивхское селение за юколой для собак, при этом удалось наблюдать действо шамана, который свои крики и кривляния завершил поеданием горячих углей. 5 марта моряки были на Де-Кастри, в том месте, где летом прошлого года Бошняк наметил место для поста. Теперь там подняли высокую мачту, над которой взвился Андреевский флаг, это означало, что земля Де-Кастри — владение России. Тунгусы и нивхи из близлежащих селений были свидетелями церемонии. Первым жилищем нового поста, который назвали Александровским, стал шалаш нивхских рыбаков. Казаки начали строить дом. Бошняк же купил лодку у нивхов, выбрав самую большую и прочную. За месяц дом был построен: соорудили печь из глины, окна вместо стёкол затянули тонкой тканью — миткалём.

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

И вот настал день 23 мая 1853 года. Лейтенант Николай Бошняк со спутниками подошёл к еле заметному низкому перешейку, за которым открывалось обширное водное пространство. Это и был залив Хаджи. Где-то должен быть вход в залив, но открытие было настолько важным, что ждать никто не захотел: лодку дружно перетащили через перешеек. Удивительно было после довольно бурного моря оказаться в обстановке полного штиля. Поверхность воды в заливе, закрытом от ветров, была абсолютно спокойна. Путешественники сразу же приступили к описанию залива, задерживаться долго было нельзя, потому что почти не осталось продуктов.

Залив состоял из нескольких бухт. Бошняк все их описал и дал названия. Сам залив Хаджи получил имя императрицы Александры. Самая удивительная бухта — длинная, зигзагообразная, похожая на канал, закрытая от ветров скалистыми берегами — Константиновская — была выбрана для основания поста. Место обозначили высоким крестом, на котором Бошняк вырезал: «Гавань императора Николая, открыта и глазомерно описана лейтенантом Бошняком 23 мая 1853 года на туземной лодке со спутниками казаками Семёном Парфентьевым, Киром Белохвостовым, амгинским крестьянином Иваном Мосеевым».

31 мая лодка под парусом, наполненным попутным южным ветром, вышла из залива. Путешественники возвращались, питаясь одной лишь рыбой и ягодами, собранными на берегу. Через 6 дней они уже были на берегу залива Де-Кастри. Здесь Бошняк привёл в порядок свои записи и карты. Доклад Невельскому он отправил с казаком Парфентьевым. Через неделю по приказу Невельского приехал на смену мичман Разградский. Бошняк отправился в Николаевский пост, где узнал много нового. Главное — изменилось отношение правительственных кругов к дальневосточным «самоуправным делам» Невельского. После того как в марте 1853 года англо-французская эскадра вошла в Чёрное море, в Петербурге поняли, что Амурская экспедиция имеет огромное государственное значение. (Это особенно стало ясно во время Крымской войны, которая, несмотря на своё название, была и дальневосточной войной: наряду с Севастополем, англо-французской эскадрой был осаждён Петропавловск-Камчатский. Укрывшийся в Императорской гавани, о которой ничего не знали интервенты, спасся от уничтожения дальневосточный флот России).