Резонно рассудив, что для нового судна нужен новый экипаж, и вновь надеясь только на удачу, Арсенин направился на Алеутскую, где располагалась контора Компании Бринера.
К его удивлению, через несколько минут после того, как он изложил одному из клерков свое желание встретиться с владельцем компании, рассчитывая в лучшем случае лишь записаться на прием, тот же клерк проводил его на второй этаж здания, где находился кабинет Бринера. Услужливо отворив перед Арсениным двери, клерк моментально исчез из поля его зрения. Бринер оказался довольно-таки высоким мужчиной лет сорока пяти. Из-за мясистого носа, окладистой бороды, пышных усов и круглого животика под черным шелковым жилетом он чрезвычайно напоминал Александра Дюма-отца и Жюля Верна, вместе взятых. Говорил он по-русски очень чисто и почти без акцента, разве что иной раз несколько непривычно ставил ударения в словах.
Бринер произвел на Арсенина впечатление человека, с одной стороны, в высшей степени делового, умного и обязательного до скрупулезности, с другой — авантюриста. Человек, бежавший за романтикой дальних странствий из родной Швейцарии, не имеющей выхода к морю, проведший юность юнгой на пиратском корабле и торговцем шелком в Йокогаме, без сомнений заслуживал уважительного к себе отношения.
После часового разговора, прошедшего хоть и в насквозь деловом, но дружелюбном тоне, Арсенин и Бринер договорились о встрече через день, когда кандидат на должность должен принести свои рекомендации и дипломы. Вторая встреча заняла несколько больше времени и закончилась для Арсенина самым наилучшим образом. Ознакомившись с рекомендациями, выданными Доброфлотом, а также основываясь на полученной им лично информации, Бринер утвердил Всеслава в должности капитана грузо-пассажирского парохода «Натали», переименованного из «Аделаиды» в честь жены Бринера Натальи Иосифовны Куркутовой.
Позднее, уже набравшись жизненного опыта, Арсенин понял, что Бринер, собиравшийся открывать совместное дело с купцом второй гильдии Кузнецовым, стремился иметь доход, не зависимый от успеха либо неуспеха нового предприятия.
Вплоть до середины июня 1891 года Арсенин занимался комплектованием экипажа, вопросами мелкого ремонта и полного оснащения своего нового судна. Если, служа в должности старпома, он считал, что основная часть работы падает на его плечи, то теперь он придерживался абсолютно иного мнения. И хотя офицера на должность старпома он нашел достаточно быстро, работы хватало обоим. К концу июня команда закончила все работы. Экипаж укомплектован, судно оснащено и готово к походу, и посему, затратив два дня на получение груза и коносаментов, 1891 года июня месяца двадцать второго числа «Натали» вышла в свой первый рейс в порт Суэттенхем, прошедший без каких-либо происшествий.