На карте Львова 1726 г. неплохо показаны и Курильские острова, но почему-то нет Сахалина.
Одновременно с представлением карты Шестаков подал проект большой экспедиции для исследования северо-восточных окраин Сибири. Как указывает М. С. Боднарский, проектом Шестакова предполагалось: 1) покорить незамиренных еще коряков на северных берегах Охотского моря и чукчей за Анадырем; 2) обследовать западные берега Охотского моря и лежащие против них острова вплоть до китайской границы; 3) найти прямой путь из Удского острога через море к западному берегу Камчатки и Курильским островам; 4) обследовать Курильские острова; 5) пройти с западного берега Камчатки мимо мыса Лопатки к устью Анадыря и 6) разведать Большую Землю (Америку) против Чукотской земли[93].
Боднарский отмечает, что громадный размах проектируемой экспедиции нисколько не смущал Шестакова, «как не смущали пространства и землепроходцев старого времени».
В Петербурге проект Шестакова был поддержан обер-секретарем Сената Иваном Кирилловичем Кириловым, были отпущены снаряжение и средства, подобран основной личный состав. Шестакова назначили главным начальником Северо-восточного края.
В 1728 г. Шестаков во главе большого отряда прибыл в Охотск и здесь занялся постройкой для экспедиции двух ботов: «Восточный Гавриил» и «Лев». Кроме того, в распоряжение Шестакова поступили суда Первой Камчатской экспедиции Беринга – шитик «Фортуна» и бот «Св. Гавриил».
Экспедиция А. Ф. Шестакова протекала неудачно. Сам он в 1729 г. был убит в схватке с чукчами. Бот «Лев» во время зимовки был сожжен коряками.
Командование экспедицией перешло к капитану Дмитрию Павлуцкому, который в 1730 г. направил «Св. Гавриил» и «Восточный Гавриил» на поиски Большой Земли к востоку от Камчатки. Бот «Св. Гавриил» под командой Ивана Шестакова (племянника А. Ф. Шестакова) исследовал Удскую губу и плавал в Охотском море до Камчатки. Осенью 1730 г. И. Шестаков сдал «Св. Гавриил» штурману Якову Генсу, готовившемуся к плаванию к Северо-западной Америке. Летом 1731 г. Генс перешел в Большерецк, а в 1732 г. в Нижне-Камчатск, где из-за тяжелой болезни сдал «Св. Гавриил» подштурману Ивану Федорову.
Бот «Восточный Гавриил» осенью 1730 г. разбился у юго-западных берегов Камчатки в 30 км от Большерецка.
Шитик «Фортуна» под командованием Василия Афанасьевича Шестакова (сына А. Ф. Шестакова) плавал к Курильским островам, на которых занимался сбором ясака.