Однако слова не сдержал, вновь взялся за оружие (на этот раз получив чин генерала артиллерии) и в мае 1769 года опять оказался в русском плену. Суд приговорил его к ссылке на поселение в Казань. Оттуда Беньовский бежал вместе с пленным шведским майором Адольфом Винбладом, также служившим в войсках Барской конфедерации. Беглецы пробрались в Петербург, проникли в порт и, выдав себя за отставших от корабля английских матросов, нанялись на купеческий галиот, отходивший за границу. Однако капитан корабля, заподозрив недоброе, выдал их петербургской полиции. Специальная комиссия Сената под председательством генерал-прокурора А. А. Вяземского приговорила беглецов к ссылке на Камчатку.

В декабре 1769 года осужденных отправили по этапу. Вместе с ними шли полковник И. Батурин, собиравшийся в свое время совершить дворцовый переворот против Елизаветы Петровны в пользу будущего царя Петра III, еще бывшего тогда наследником престола, и офицеры В. Панов и И. Степанов, замышлявшие переворот против Екатерины II в пользу цесаревича Павла (будущего императора). Лишь в октябре 1770 года Беньовский и его товарищи добрались до Охотска. На судне тотемского купца Холодилова их доставили в Большерецкий острог — одно из первых русских поселений на Камчатке. Уже тогда, во время девятидневного морского перехода из Охотска в Большерецк, у Беньовского возникла мысль о захвате корабля, но он не сумел осуществить свой план. Большерецкий острог был небольшой деревушкой с церковью и комендантским домом. Несколько десятков казаков несли здесь гарнизонную службу. Возглавлял острог капитан Нилов. До того как Беньовский попал в Большерецк, там уже находилась одна партия ссыльных. В нее входили попавший сюда еще в 40-х годах камердинер регентши Анны Леопольдовны А. Турчанинов, сосланные в начале 60-х годов гвардии капитан И. Хрущев и поручик С. Гурьев, обвиненные в подготовке дворцовых переворотов, а также еще несколько человек. Беньовский вскоре подружился с ними. Комендант Нилов пригласил его учителем к своему двенадцатилетнему сыну. Там Беньовский познакомился еще с одним юношей — сыном местного попа В. Устюжаниновым, впоследствии одним из его ближайших сподвижников.

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