После женитьбы Шелехов решил открыть собственное дело в Охотске.
Этот город располагался на берегу залива при впадении рек Охоты и Кухтуя в море. Город являлся портом для кораблей купеческих компаний, где их строили и чинили. Однако сам порт отличался большими неудобствами: вход в устье реки был усеян отмелями, слабый грунт не позволял достаточно хорошо встать на якорь, а фарватер реки каждый год изменялся. Все это вело к частой поломке кораблей, причем у самого входа в порт.
Несмотря на сырой и холодный климат, туманы и дожди, недостаток хлеба и свежих продуктов, сибирские мореходы и промышленники продолжали приезжать в Охотск, привлеченные выгодным пушным промыслом на Тихом океане.
После своего приезда в Охотск Шелехов в компании с охотскими купцами почти ежегодно стал снаряжать корабли для промысла морского зверя: только за пять лет (1776–1781 гг.) он снарядил около десяти судов, что принесло ему немалый доход.
Район самих промыслов постепенно перемещался на восток, к Лисьим островам и побережью Аляски. Наблюдая, как распадаются старые купеческие компании, как быстро возникают новые и как неблагоприятно сказывается все это на развитие русского мореплавания, пушного промысла и торговли на Тихом океане, Шелехов стал понимать, что деятельность русских промышленников и мореходов на Тихом океане следует организовать по-новому.
Шелехов не мог не замечать, что на Тихом океане все более разворачивается соперничество между мировыми державами за доминирующую роль, и не мог не понимать, — для того чтобы в этой борьбе Россию не вытеснили из океана, ей нужно иметь там надежные базы с постоянными жителями из русских людей.
Зимой 1781 года в разговоре со своим бывшим хозяином И.Л. Голиковым Шелехов предложил образовать постоянную компанию у берегов Америки на срок десять лет. На средства этой компании должны были снаряжаться корабли в самые отдаленные места Тихого океана. Северо-американское побережье нужно было официально присоединить к России и основать здесь постоянное поселение. Жители Русской Америки должны были не только заниматься рыбной ловлей и охотой на морского зверя, но и сеять хлеб, изучать недра этой земли.
Русские поселенцы должны были находиться в дружеских сношениях с аборигенами, работать с ними рука об руку, обучать грамоте. Из аборигенов должны были выходить толмачи (переводчики), мореходы и специалисты по самым разным ремеслам.
Корабли торговой компании должны каждый год вывозить в метрополию пушнину из Русской Америки и отвозить сюда же все необходимое для поселенцев.
Голиков с удивлением выслушал идеи Шелехова, но после долгих раздумий решил войти в торговую компанию.
Шелехов решил сам руководить плаванием торговых кораблей к берегам Русской Америки, поскольку понимал, что именно ему, инициатору этого проекта, и следует проводить его в жизнь.
В Охотске, в устье верфи реки Урала Шелехов заложил три судна. Это были галиоты — двухмачтовые острокильные парусные суда.
Шелехов сам следил за постройкой галиотов, заготовлял необходимые грузы, вел переговоры с местными купцами и губернскими чиновниками. К лету 1783 года три галиота «Три Святителя», «Симеон и Анна» и «Св. Михаил» были спущены на воду. Во главе каждого судна стояли опытные командиры. Экипажи всех трех кораблей насчитывали 192 человека.
Шелехов понимал, что высадка должна была совершиться далеко на востоке, где еще было немало морского зверя. Чтобы не блуждать в море, рассчитывая сделать случайные открытия, Шелехов решил совершить высадку в достаточно известном месте, поскольку этот пункт должен был позволить русским промышленникам продвинуться вперед. Первое русское поселение он решил основать на острове Кадьяк. Это был самый крайний пункт, куда доходили русские промышленники и мореходы. Эти места изобиловали бобрами, за которыми охотились местные жители — эскимосы.
Сам остров лежал около северо-западного побережья Америки и был отделен проливом от Аляски. К северу от Кадьяка на расстоянии 150 км находится полуостров Кенай. К северу, северо-востоку и востоку от Кадьяка огромной дугой тянется северо-западное побережье Северной Америки.
16 августа 1783 года галиоты вышли из устья Урала в море.
Пятнадцать дней корабли плыли к Курильским островам. Плавание затрудняли частые шторма, штили и встречные ветры. Огонь сигнальных фонарей был невидим из-за густого тумана.
31 августа экипажам галиотов открылась густая цепь Курильских островов. Запасшись у первого острова Шумшу пресной водой, суда прошли первым Курильским проливом и, обогнув мыс Лопатку, взяли курс на северо-северо-восток, к острову Беринга.