Адмиралтейств-коллегия обратила внимание на храброго офицера. Когда, по предложению великого русского ученого М. В. Ломоносова, началась подготовка Восточной морской экспедиции, которая должна была исследовать "новооткрытые острова в Восточном океане", Адмиралтейств-коллегия выдвинула кандидатуру Петра Кузьмича Креницына на пост руководителя этой экспедиции.
Год рождения П. К. Креницына неизвестен. Первые сведения о нем относятся к 16 октября 1742 года, когда он поступил учеником в Морскую Академию. По-видимому, Креницыну было в это время не менее двенадцати лет. Через год, в 1743 году, он был произведен в гардемарины.
В течение девяти лет (с 1745 по 1753 год) Креницын служил на Балтийском море. За это время он был произведен сначала в мичманы (1748), а затем в унтер-лейтенанты (1751).
В 1754 году Креницын был произведен в корабельные секретари и два года исполнял обязанности аудитора (военного юриста) в комиссии военного суда. В 1756 году Креницын вернулся во флот и на корабле «Астрахань» совершил переход из Архангельска в Кронштадт. В следующем году он был произведен в лейтенанты и до 1760 года плавал командиром пинка «Кола» на Балтийском море.
Командиром бомбардирского корабля «Юпитер» его назначили 19 мая 1760 года. В апреле 1762 года Креницын был произведен в капитан-лейтенанты, а месяц спустя назначен командиром тридцатидвухпушечного фрегата «Россия». В этой должности он находился вплоть до назначения его руководителем Восточной экспедиции.
Интерес русских промышленников к "Восточному океану", к островам, открытым А. И. Чириковым в 1741 году, начал особенно проявляться в середине XVIII века. В начале 60-х годов XVIII века камчатские власти, а через них и сибирский губернатор, знали о том, что между Командорскими островами и Америкой лежат, по крайней мере, две группы островов: ближние с прилегающими к ним на востоке Крысьими островами и отдаленные, примыкающие к Америке Лисьи острова (включающие "остров Аляксу"). Так как основная часть Андреяновских островов тогда еще не была открыта, то между обеими островными группами предполагался большой разрыв.
В 1764 году по инициативе Ломоносова началась организация Северной якобы промысловой правительственной экспедиции с секретным заданием "для пользы мореплавания и купечества на восток… учинить поиск морского проходу Северным океаном в Камчатку". Экспедицию возглавил В. Я. Чичагов. Предполагалось, что эта экспедиция встретится в Тихом океане с экспедицией П. К. Креницына; для встречи были предусмотрены специальные опознавательные сигналы и пароли.
В мае 1765 года три судна, специально построенные для плавания в полярных морях, вышли под командованием Чичагова из Колы на север.
В начале августа они достигли 80°26 северной широты (к северо-западу от Шпицбергена). Продвинуться дальше из-за тяжелых льдов им не удалось, и Чичагов привел свой отряд в Архангельск. В 1766 году Чичагов повторил «поиск», но продвинулся лишь немногим дальше — до 80°30 .
Таким образом, предполагавшаяся встреча двух русских экспедиций в Тихом океане не состоялась.
Вторая экспедиция была организована после того, как Екатерина II в связи с проектом Ломоносова и докладом Чичерина приказала Адмиралтейств-коллегий "отправить немедленно по своему рассуждению, сколько надобно, офицеров и штурманов, поруча над оными команду старшему, которого б знание в морской науке и прилежание к оной известно было". Несомненно, что основной задачей этой экспедиции было не только описание открытых островов (к которым относили и Аляксу), но и формальное и фактическое закрепление их за Российской империей, приведение «американцев» (алеутов) в Российское подданство, урегулирование сбора ясака и контроль за промышленниками, имевший целью не допустить нарушения интересов казны.
Официально эта экспедиция называлась "Экспедицией о возобновлении китовых и других звериных и рыбных промыслов".
Офицеры, участвовавшие в экспедиции, тем же указом Екатерины II были поставлены в исключительно привилегированное положение. Одновременно с назначением в эту экспедицию они повышались в чине "с приобщением при том вечного пенсиона против получаемого по чину в оном пути жалованья, независящего от впредь положенного по чину оклада". Кроме того, им определялось на время участия в экспедиции двойное жалованье на том основании, что "не могут они, в таком отдалении будучи, смотрение иметь за своею собственною экономиею".
Начальником этой экспедиции и был назначен Креницын, произведенный в связи с этим назначением в капитаны 2-го ранга и награжденный золотыми часами. Креницыну разрешалось самому выбрать себе помощника, и он указал на Михаила Дмитриевича Левашева, с которым вместе участвовал в Кольбергской операции. Это был самый удачный выбор: Левашев полностью оправдал оказанное ему доверие.
Михаил Дмитриевич Левашев (точный год рождения неизвестен) осенью 1751 года поступил учеником в Морскую Академию, а через два года был определен в Морской корпус кадетом. С 1755 по 1762 год он прослужил в Балтийском флоте, в 1757 году был произведен в гардемарины, через год в мичманы, а после Кольбергской операции (в 1762 году) — в унтер-лейтенанты. 1 июля 1764 года ему присвоили очередной чин — капитан-лейтенанта и наградили золотыми часами.
Цели и задачи восточной экспедиции держались в тайне: официально она именовалась "Экспедицией для описи лесов по рекам Каме и Белой". Формально она была подчинена сибирскому губернатору Чичерину, которому Екатерина II в своем рескрипте от 28 мая 1764 года предписывала: "…Повелеваем вам на то употреблять из первых вступивших денег сколько потребно, присылая для известия оным счет в Адмиралтейскую Коллегию".
Действительно, на снаряжение экспедиции были отпущены очень большие для того времени средства — 100 837 рублей.
Об истинных целях экспедиции, которой ему надлежало руководить, Креницын узнал только 17 сентября 1764 года из инструкции сибирского губернатора, полученной им в Тобольске, куда он прибыл вместе с Левашевым, семью штурманами и двумя подштурманами. В этой инструкции Чичерин писал: "…За главнейшее основание порученной вам экспедиции поставляю несколько уже известных, сысканных купцами, Алеутских островов, основательное описание и положение оных на карту сделать, а особливо большого и многолюдного острова Кадьяк; приложив всевозможное старание, обходя его вокруг, писать весьма нужно, остров то или матерая земля, ибо на показания бывших на том острову наших людей утвердиться не можно".
Участники экспедиции привезли из Петербурга несколько карт района Алеутских островов, в том числе карты, составленные экспедицией Беринга — Чирикова и купцом Петром Шишкиным. Из навигационных инструментов они доставили двенадцать морских квадрантов.
В Тобольске к экспедиции были прикомандированы десять штурманских учеников из местной навигационной школы и команда из "нижних чинов". Экспедицию снабдили необходимыми материалами и припасами.
В начале марта 1765 года экспедиция в полном составе выехала из Тобольска и в октябре прибыла в Охотск.
В Петербурге очень внимательно следили за действиями отряда Креницына. Сохранились документы, свидетельствующие о том, что Екатерина II лично интересовалась этой экспедицией и возлагала на нее большие надежды. "С нетерпением ожидаю, что далее произойдет", — писала она Чичерину осенью 1765 года.
Когда экспедиция прибыла в Охотск, оказалось, что строящиеся для нее по приказу Чичерина два судна еще не готовы. Креницын обвинял в этом командира Охотского порта Ртищева, а затем сменившего его Плениснера; небезынтересно отметить, что на последнего в то время жаловались и промышленники за то, что он "во отправлениях на промыслы под разными видами их удерживает и тем желаемому успеху препятствует". Постройка судов закончилась только в августе 1766 года. Кроме них, экспедиции передали еще два судна из числа приписанных к Охотскому порту — галиот "Св. Павел" и бот "Св. Гавриил". Командование большим из построенных судов — бригантиной "Св. Екатерина" Креницын принял на себя. Командиром второго, меньшего судна, — гукора "Св. Павел" — он назначил Левашева, командиром галиота — штурмана Дудина 2-го, командиром бота — штурмана Дудина 1-го.
Из Охотска суда вышли 10 октября 1766 года. На третий день плавания, отойдя от Охотска всего лишь на несколько десятков километров, суда потеряли друг друга из виду.
Потерпев небольшую аварию, "Св. Екатерина" 22 октября достигла Большерецка (на западном побережье Камчатки) и стала на якорь. В ночь с 23 на 24 октября штормовой западный ветер понес бригантину на берег и выбросил левым бортом на мель.
Едва команда успела высадиться, как ударами волн бригантина была совершенно разбита. Экспедиция лишилась самого большого судна.
