Кроме уже упоминавшихся выше Вильно, Киева и Житомира Бестужев-Рюмин много раз бывал в Тульчине, Каменке и Линдах — месте квартирования штаба Вятского пехотного полка, которым командовал Пестель. В 1823 году он тайно ездил в Москву, бывал и в Хомутце — полтавском имении Муравьевых-Апостолов, и в Умани — месте службы князя Волконского. Месяцами он жил в Василькове у Сергея Муравьева.
Между тем дисциплина требовала нахождения всех офицеров при полку, в отношении же бывших семеновцев, сосланных на юг после «истории» 1820 года, лишенных права не только на отставку и отпуск, но даже и на командировку, это правило должно было действовать и вовсе без исключений.
На следствии Тизенгаузен убедил себя в том, что виновником всех его бед был именно Бестужев-Рюмин. И пытался дать ответ (не только следствию, но прежде всего самому себе), как же он, в общем, уже немолодой полковник, поддался обаянию обер-офицера и не только не «отстал» от общества, но и постоянно нарушал воинскую дисциплину. Практически в каждом своем показании он сам — без давления Следственного комитета — возвращается к этой теме.
«Несмотря на либеральные идеи Бестужева, — пишет он в одном из таких показаний, — я всегда его считал за пустого и нимало не опасного для общества офицера. Суждения его мне всегда казались столь странными, что я часто над оными смеялся и принимал за бредни. Он никогда почти не выдерживал моего взгляда, и мне кажется, что он меня очень боялся; ибо почти всегда, когда я только начинал укорять его за бессмысленные его рассуждения и неосновательность оных ему доказывать, то он обыкновенно молчал, по-тупя взор вниз. Вижу, и ясно, что я в нем ошибался, и сильно ошибался! Кто в состоянии проникнуть все изгибы черной души?»
Это показание весьма примечательно. Если не принимать во внимание его эмоциональный тон, то надо признать, что Тизенгаузен довольно точно описывает характер своих отношений с Бестужевым-Рюминым. Действительно, скорее всего, начались эти отношения с насмешек старшего и опытного полковника над молодым прапорщиком. Однако Тизенгаузен ошибается, и ошибается действительно сильно, утверждая, что Бестужев его боялся. Его подчиненный был в тайном обществе на равных не только с полковниками, но и с генералом Волконским; к его мнению прислушивался Пестель, он вел сложнейшие переговоры с Польским обществом. По заговорщицкой «табели о рангах» Бестужев-Рюмин был на две ступени выше Тизенгаузена.
Видимо, Бестужев быстро нащупал «слабую струну» своего полкового командира: Тизенгаузен кичился перед ним опытностью, считал себя вправе поучать его, «укорять» за «бессмысленные рассуждения». Бестужев же не возражал, умело играя роль покорного слушателя, — «молчал, потупя взор вниз». И взамен получал не только полную свободу передвижения, но и казенные подорожные: путешествовать иначе, «частным образом», бывший семеновец не мог.
С Сергеем Муравьевым-Апостолом Бестужева-Рюмина связывали близкая дружба и родственные узы: мать Бестужева состояла в кровном родстве с мачехой Муравьева. Познакомились же и подружились они в конце 1810-х годов, во время совместной службы в Семеновском полку. «Муравьев мне показал участие, и мы подружились, — показывал Бестужев на следствии. — Услуги, кои он мне в разное время оказывал, сделали нашу связь теснее». Пылкость взаимоотношений Муравьева и Бестужева подчас вызывала удивление и неприятие у современников. Так, например, в одном из писем к брату Матвей Муравьев-Апостол, сетуя на то, что Сергей говорит о Бестужеве-Рюмине «не иначе, как со слезами на глазах», называл его «мнимым другом». А генерал Михаил Орлов выразился еще более хлестко: «Около Киева жили Сергей Муравьев и Бестужев, странная чета, которая целый год хвалила друг друга наедине».
Однако в делах тайного общества Муравьев и Бестужев-Рюмин отнюдь не составляли единого целого. Между ними существовали и политические разногласия: Муравьев не одобрял радикализма своего друга по вопросу о судьбе императорской фамилии. В 1823 году Бестужев, вняв убеждению Пестеля, дал согласие на «убиение» императора, Муравьев же долго противился этому. Не нравилась Муравьеву и бестужевская решительность при решении вопроса о судьбе цесаревича Константина. Когда Бестужев-Рюмин, исполняя отданный «именем Директории» приказ Пестеля, стал требовать от поляков «немедленного истребления цесаревича», Муравьев заметил своему другу: «Зачем хочешь ты взять на себя преступления другого народа, не довольно ли уже того, что мы вынуждены были согласиться на смерть императора?»