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