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

3 августа корабли подошли к острову Кадьяк, зашли в Павловскую гавань, но тут подверглись нападению индейцев племени коняги. Защищаясь, им пришлось произвести выстрел из пушки, который поверг аборигенов в ужас — бежали в панике. Более четырёх сотен взяли в плен. Несмотря на первый конфликт, вскоре удалось наладить отношения с индейцами. Шелихов посетил их селение неподалёку от гавани. «Пришёл к ним жить в дружбе, — писал он, — не вести войну... притом же и всемилостивейшая наша государыня Екатерина II... доставит им жизнь безопасную и спокойную... многие примеры ласкового обхождения и малые подарки совершенно их усмирили».

Особенно помогла развитию взаимопонимания русских поселенцев и аборигенов последующая деятельность Шелихова. Прежде всего он занялся устройством жилья местного населения на европейский манер, обучал возделыванию земли и выращиванию овощей. «Я показал им способность и выгоды российских домов и платья, и употребления пищи. Они видели труды моих работных, когда они копали землю на огороде, сеяли и садили семена; по созревании плодов я велел им оные раздавать... Многих я велел кормить изготовленною работными моими для себя пищею, к чему они крайне чувствовали охоту. Таково моё с ними поведение час от часу более их ко мне привязывало».

Но не всё аборигены воспринимали как должно. «Почитали они чудом скороспешное строение у нас домов... Невежество их так велико, что они, когда мы во времена тёмных ночей выставляли бывший у меня кулибинский фонарь, думали, что то было солнце, которое мы похищали...»

Православный Шелихов занимался и миссионерской деятельностью: в первый же год обратил в православную христианскую веру 40 человек. Он организовал школу для обучения грамоте. «Начал я вводить их в познания о книгах и обещая выучить и детей их, ежели кто из них на то согласитца таковой же, по их мысли, премудрости... Должно отдать народу сему справедливость в остроте ума, ибо дети их весьма скоро понимали свои уроки, и некоторые до отъезду моего столь выучились по-российски говорить, что без нужды можно их разуметь». Двадцать пять индейских мальчиков обучил во время зимовки на Кадьяке Шелихов.

В целом зима прошла благополучно, но цинга не миновала — несколько человек умерли. В мае Шелихов на четырёх байдарах отправился на восток. На суда погрузились 110 индейцев из племени коняги, 11 алеутов и 52 русских промышленника. Шелихов повёл суда к американскому берегу. Затем опять зимовка на Кадьяке. На сей раз и зимой продолжались походы по острову и американскому берегу. Всюду, где было возможно, строились жилища, в которых оставались промышленники.

Наконец, стала известна судьба исчезнувшего два года назад «Архистратига Михаила» под командой Олесова. Корабль с опозданием прибыл зимовать на Уналашку, а весной шторма и поломка мачты не позволили ему покинуть остров. Пришлось зимовать. К Шелихову отправились на шлюпке 30 человек, но штормом их отнесло к берегу американского материка, где и прошло шесть недель. Одиннадцать человек погибли, остальных спас отряд промышленника Евстрата Даларова.

Тем временем Шелихов распорядился построить крепости на мысе Св. Ильи, а также в Чугацком заливе и на острове Афогнак. И составить опись побережья. Для утверждения принадлежности земель России он велел «ставить кресты и закапывать в землю обломки горшечные, кору берёзовую и уголья».

Сам Шелихов шёл с островов на «Трёх Святителях» в Охотск, а правителем русских поселений на американском берегу, где находилось 163 промышленника, и Алеутских островах оставил енисейского купца Константина Самойлова. Он наказал ему «поступать расселением российских артелей для примирения американцев в прославлении Российского государства на изъяснённой земле Америке и Калифорнии до 40-х градусов (северной широты)».

По пути к Камчатке Шелихов встретил «Михаила» и приказал вести судно на остров Афогнак, сам же пошёл вдоль Алеутских островов. Согласившиеся плыть в Россию алеуты исполняли обязанности матросов (почти вся команда болела цингой). Шелихов достиг Камчатки в устье реки Большой и стал на якорь у посёлка Большерецк; судно сорвало с якоря, когда он был на берегу. «Трёх Святителей» унесло в море, и корабль пошёл в Охотск без командира, а Шелихов на байдарке доплыл до Петропавловска.

В Охотск Шелихов прибыл с оленьим караваном через север Камчатки, а потом — вдоль побережья Охотского моря. Только 27 января 1787 года он, наконец, достиг Охотска, там встретился с женой и детьми, остававшимися на галиоте «Три Святителя», а ещё через полтора месяца добрался до Иркутска. Дальнейший путь лежал в Петербург, где Шелихов собирался официально закрепить освоенные им американские земли.

Вместе с купцом Голиковым Шелихов обратился к Екатерине II с прошением: 20 лет монопольно промышлять на Алеутских островах и побережье Северо-Западной Америки. Купцы просили от государства беспроцентную ссуду 200 тысяч рублей. С нетерпением ждали они ответа из Зимнего дворца. Екатерина II внимательно ознакомилась с представленными ей бумагами. Но реакция её была отрицательной. «В казне теперь нет денег никаких», — ответила она на просьбу о займе 200 тысяч рублей. Императрице не понравилось также, что купцы хотели монополизировать торговлю: «...исключительная торговля противное моим правилам». Но главное — она не одобрила саму идею приобретения Россией новых владений в Тихом океане: «Многое распространение в Тихом море не принесёт твёрдых польз. Торговать дело иное, а владеть дело другое».

Екатерина II отказала и в праве использовать на службе Американской компании морских офицеров и артиллерии. Шёл 1788 год. Императрица словно предвидела, что через 79 лет русское правительство добровольно откажется от американских владений, ссылаясь на то, что удержать их нелегко.

Но купцы-просители всё же были одарены монаршими наградами: за свои труды на пользу отечества они получили шпаги, медали и почётные грамоты...

Шелихов возвратился в Иркутск и позже в Охотск.

Он решил продолжать своё дело и без царской ссуды. Галиот «Три Святителя» отправляется на Алеутские острова. На нём плывёт Евстрат Даларов, которому Шелихов поручил позаботиться о русских поселениях на островах, об укреплении связей с аборигенами, а также продолжать исследование островов и американского побережья, разводить скот, возделывать огороды.

В летние месяцы 1788 года галиот совершал плавания вдоль американского побережья: исследовался берег залива Аляска, между полуостровом того же названия и собственно материком Северной Америки. Именно в этой огромной акватории площадью больше миллиона квадратных километров находились архипелаги Кадьяк, Александра и Королевы Шарлотты. Мореходы Герасим Измайлов и Дмитрий Бочаров открыли с борта «Трёх Святителей» обширные заливы Якутат и Нучек. Всюду, где они высаживались на берег, в соответствии с указаниями Шелихова зарывали в землю медные доски с российскими гербами и надписью «Земля Российского владения». В заливе Якутат местному вождю (тойону) Илхаки мореходы подарили портрет наследника престола Павла и медный герб империи.