Однако «дурак» и «взбалмошный мальчик» очень быстро заставил считаться с собою умных и рассудительных старших коллег по заговору. Выяснилось, что среди заговорщиков появился новый яркий лидер. Друг Сергея Муравьева, имевший на него немалое влияние, он в то же время сумел добиться уважения и доверия Пестеля. В Южном обществе Бестужев-Рюмин стал известен как неутомимый агитатор, пламенный оратор, зажигавший своими экзальтированными речами немалые аудитории, в том числе и изначально враждебно настроенные. Правилам ораторского искусства его еще в детстве научил Алексей Мерзляков — профессор Московского университета, автор знаменитого в свое время учебника риторики, выдержавшего несколько изданий. Мерзляков был одним из домашних учителей Бестужева-Рюмина.
В 1823 году Пестель, предупредив начинающего конспиратора о возможности получить «несколько пуль в лоб», если тот решится на предательство, поручил ему первое серьезное задание — вести (вместе с Сергеем Муравьевым) переговоры с Польским патриотическим обществом о совместных действиях. Переговоры эти Бестужев провел сам: Сергею Муравьеву они были неинтересны.
Собственно, платформа для объединения обществ была. Согласно «Русской Правде», Польша в случае победы русской революции получала независимость, а независимость поляки считали главной целью своего заговора. «Должна Россия даровать Польше независимое существование», — гласил программный документ Южного общества. Однако на практике польская независимость означала отторжение от России немалых территорий. И многие члены русского тайного общества оказались к этому не готовы. Тот же Михаил Орлов, узнав о переговорах, сказал Бестужеву: «Вы сделали вздор и разрушили последнюю нить нашего знакомства. Вы не русский; прощайте».
Бестужева-Рюмина это не остановило. Похоже, он считал, что независимость Польши — не слишком высокая цена помощи поляков при подготовке и проведении русской революции.
Переговоры с Польским патриотическим обществом проходили успешно. Выполняя данное ему поручение, Бестужев предложил полякам заключить устный договор, текст которого он представил для окончательного утверждения в Директорию. Согласно этому договору, Польше предоставлялась независимость, при этом поляки могли «рассчитывать на Гродненскую губернию, часть Виленской, Минской и Волынской». Кроме того, русские заговорщики брали на себя обязанность «стараться уничтожить вражду, которая существует между двумя нациями», считая, что «в просвещенный век» интересы «всех народов одни и те же и что закоренелая ненависть присуща только варварским временам».
Поляки же, в свою очередь, обязаны были признать свою подчиненность южной Директории, начать восстание в Польше одновременно с восстанием русских, помешать великому князю Константину вернуться в Россию, блокировать расквартированные на территории Польши русские войска. Польское патриотическое общество обязывалось предоставить русским заговорщикам сведения о европейских тайных обществах, а также после победы революции «признать республиканский порядок». За успехи в переговорах с поляками Директория Южного общества выразила Бестужеву-Рюмину благодарность.
Кроме ораторского дарования подпоручик Бестужев-Рюмин обладал и незаурядным актерским талантом. Это хорошо видно из истории его взаимоотношений с собственным полковым командиром, полковником Василием Тизенгаузеном.
Василий Тизенгаузен был в 1824 году принят в Южное общество Сергеем Муравьевым-Апостолом. Среди декабристов он был одним из самых старших, к 1826 году ему уже исполнилось 46 лет. За плечами полковника был немалый боевой опыт: в армии он начал служить с 1799 года, в доенных действиях принимал участие с 1808 года.
Принятый в общество всего лишь с правами «брата», Тизенгаузен не был убежденным заговорщиком, желание «порвать» с заговором возникало у него постоянно. Чтобы быть подальше от Васильковских лидеров, он добивался перевода в другой полк или возможности выйти в отставку. «Подполковник Муравьев при брате своем и, помнится, при подпоручике Бестужеве-Рюмине на коленях усерднейшим образом просил меня неотступно оставить намерение мое», — показывал Тизенгаузен на следствии.
Причем Васильковским лидерам, чтобы удержать полковника от исполнения его «намерений», пришлось даже прибегнуть к помощи Пестеля. «Просили меня Бестужев и Муравьев в разговоре с Тизенгаузеном прилагать много жару и говорить о начале действий в 1825 году… ибо по его характеру сие им нужно», — показывал Пестель.
Потом, после ареста в январе 1826 года, Тизенгаузен понял, что главная его вина состояла не в участии в заговоре как таковом, а в попустительстве «преступным предприятиям» подпоручика Бестужева-Рюмина. Пользуясь этим попустительством, Бестужев имел прекрасную возможность путешествовать по делам общества по Украине, Польше и России. «Он был главным связующим звеном между заговорщиками», — утверждал начальник штаба 1-й армии барон Толь, и эти слова были справедливы.