Рассказы казачьего головы о Камчатке, Курильских островах и землицах у Северо—Восточных окраин заинтересовали видных сановников: министра Рагудзинского, вице—адмирала Сиверса и других. В 1725 году Сиверс пишет любимцу Петра Александру Меньшикову: «явился из Сибири казачий голова Шестаков, который мне объявил про тамошние дела многие неисправления. Того дня я рассудил оного до вашей светлости рекомендовать. Еще оный Шестаков имеет донести о состоянии тамошних земель… также о Камчатке и о Японских островах, похоже как я от него слышал, те места довольно знает и об них имеет карту особливую».
После встречи с Меньшиковым Шестаков представил в Сенат свой проект экспедиции. В нем был детально разработан тактический план похода – вплоть до расчета сметы по этапам экспедиции. Историк русского морского флота В.Н.Берх, характеризуя Шестакова, писал: «отличная ловкость в изъяснениях и совершенное познание описываемых им мест и предметов приобрели ему всеобщую доверенность». Изучая «особливую» карту Афанасия Шестакова, Михайло Ломоносов дал хорошую оценку познаниям казака: «Сии прекословные известия, сличив одного против другого, ясно видеть можно что положительные много сильнее отрицательных».
Карты казачьего головы вскоре исчезли. «Одну из них перерисовал и отправил в Париж известный похититель русских чертежей и записок Жозер—Николя Делиль, появившийся в Петербурге в 1726г.» – так уверяет нас писатель—историк С. Марков.
После одобрения Сенатом новой экспедиции понадобилось еще полгода на апробацию решения в высших правительственных органах, на разработку законодательных документов, на четкую формулировку мотивов, экспедиции (дальнейшее освоение новых земель и объясачивания народов Северо—Востока), а также на организационные меры. Май—июль 1727 года стали месяцами самой интенсивной подготовки к походу. Помимо Сената комплектованием и снаряжением экспедиции занимались Петербургская рентерия, полицмейстерская контора и камер—коллегия.
Активность казачьего головы удивительна. За это время лишь Сенат собирался пять раз, рассматривая его доношения, и три раза камер—коллегия, а еще другие, менее важные государственные учреждения. Тщательно и придирчиво присматривался Шестаков к будущим участникам экспедиции. И, естественно, он стремился заполучить людей не только знающих, но и сильных телом и духом. Поэтому 16 июня он выразил свое недовольство отпиской в Сенат: «…которые матрозы и присланы и те тамошнего обыкновения не знающия, от которых я опасен, чтоб в пути не разбежались».
По пути до Якутска экспедиция пополнялась материалами и людьми разного сословия. Если до Тобольска Афанасий Шестаков командовал фактически единолично, то в Тобольске его партия пополнилась крупным отрядом служилых под командой капитана Павлуцкого, который назначался к Шестакову во всех делах «сотоварищем» для управления экспедицией
