За пять лет, с 1776 по 1781 г., Шелихов сумел снарядить и отправить в дальние края десять судов. Причем в двух случаях он стал компаньоном своего бывшего хозяина Голикова. Одна из этих экспедиций была отправлена в 1779 г., когда Шелихов в компании с купцами Голиковым и Сибиряковым снарядил на промысел на Алеутские острова судно «Иоанн Предтеча». Хотя главным организатором экспедиции был Шелихов, Голиков дал на экспедицию основную часть капитала, так что Голикову в сделке принадлежало 56 паев, Сибирякову — 5 и Шелихову — 4. «Иоанн Предтеча» благополучно вернулся в Охотск в 1785 г. и доставил владельцам пушнины на 63417 рублей.
Обычно в те времена компании образовывались только для одного путешествия, и после возвращения судна с грузом доходы делились между пайщиками и компания распадалась. Шелихов решил организовать нечто более крупное и постоянное.
В 1781 г. Шелихов предложил Ивану Голикову основать постоянную компанию, по крайней мере сроком на десять лет, и по возможности добиться в Петербурге официальной санкции на исключительные права промышленной и торговой деятельности на островах и на берегах Америки. Осторожный Голиков после некоторого раздумья одобрил план Шелихова. Оба купца отправились в Петербург, где 17 августа 1781 г. образовали новую Северо-восточную компанию, к которой присоединился племянник Ивана Голикова капитан Михаил Голиков. Целью этой постоянной компании было вести пушной промысел на Алеутских островах и у берегов Северной Америки. К великому разочарованию компаньонов императрица Екатерина II отказалась предоставить им монопольные права.
Вернувшись в Охотск, Шелихов немедленно же заложил три судна-галиота на собственной верфи. Голиоты были закончены в 1783 г., и 16 августа того же года флотилия Шелихова — Голикова вышла из Охотска в свое историческое плавание к берегам Америки.
Галиоты назывались «Три Святителя», «Симеон и Анна» и «Св. Михаил». На первом отправился в опасное путешествие сам Шелихов вместе со своей отважной женой Натальей Алексеевной. Целью экспедиции было достичь большого о-ва Кадьяк, лежащего в непосредственной близости к Аляске.
На судах, не считая команды, находились 192 «промышленных», большая часть которых должна была поселиться на островах, где намечалась постройка постоянных баз.
Путешествие до о-ва Кадьяк по бурному океану продолжалось почти год, и только 3 августа 1784 г. Шелиховы прибыли к месту назначения. Зиму Шелихов провел на о-ве Беринга, где путешественники пробыли с 14 сентября до июня следующего года.
На Кадьяке Шелихов основал селение и построил крепость, а потом так же укрепил Афогнак. Русские «промышленные» с Шелиховым во главе провели на Кадьяке две зимы, и только к лету 1786 г. Шелихов решил, что его задача выполнена, и отравился в обратный путь.
Ко времени его отъезда постоянные селения и крепости были уже и на Афогнаке и на п-ове Кенай. Артели компании расселились по берегам бухт и заливов. Люди жили в добротных избах, часто окруженных частоколом.
Шелихов с женой выехали в обратный путь 22 мая 1786 г. на галиоте «Три Святителя», взяв с собой только 12 русских «промышленных» и 40 эскимосов. 30 июля путешественники добрались до первого Курильского острова, а вскоре после этого достигли устья реки Большой на Камчатке. В Америке Шелихов оставил правителем К. А. Самойлова со 163 русскими «промышленными», пионерами первых русских селений на Аляске.
Шелихов оставил правителю задание не только промышлять пушнину, но и «поступать разселением российских артелей для примирения американцев и прославления Российского государства по изъясненной земле Америке и Калифорнии». Эти задания, особенно в отношении Калифорнии, оставались невыполненными в течение 26 лет, и только в 1812 г. И. Кусковым был основан в Калифорнии Форт Росс.
В начале 1787 г. Шелихов возвращается в Охотск, а оттуда едет в Иркутск, где надеется с помощью генерал-губернатора Якоби добиться разрешения правительства продолжать начатое дело в Америке на монопольных началах. Эти свои грандиозные замыслы Шелихов изложил в докладной «Записке» губернатору Якоби, подробно описав путешествие на Алеутские острова и Аляску и приложив к ней карты. 1791 г. «Записка» Шелихова была издана в Петербурге под названием «Российского купца именитого Рыльского гражданина Григория Шелихова первое странствование с 1783 по 1787 год из Охотска по Восточному океану к Американским берегам».
Замыслы Шелихова были поистине грандиозны. Он предполагал отправлять из Охотска или Камчатки корабли в китайские порты для торговли с китайцами вместо торга в Кяхте, который был прекращен из-за дипломатических осложнений с Китаем. Мало того, он проектировал открыть торговлю с английской Ост-Индской компанией. Для этого требовалась большая поддержка правительства.