В Вятском пехотном полку, которым командовал полковник Пестель, Майборода появился в мае 1822 года. Рекомендовал штабс-капитана Пестелю поручик Николай Басаргин, который считал Майбороду отличным знатоком «фрунтовой науки». Впоследствии Басаргин всю жизнь не мог простить себе этой рекомендации.
Служба Майбороды в Вятском полку — особый период в его жизни. Очевидно, что с первых дней пребывания в полку он показал себя действительным знатоком фрунта и этим заслужил благосклонность Пестеля. Карьера его сразу пошла в гору: он получил под свою команду 1-ю гренадерскую роту и в апреле 1823 года стал капитаном. Осенью того же года за удачное участие 1-й гренадерской роты в Высочайшем смотре Пестель представил его к награде. Майборода получил первый в своей жизни орден — Святую Анну 3-й степени.
Еще через некоторое время — в августе 1824 года — Пестель принял Майбороду в тайное общество.
Принятию Майбороды в общество пытался воспротивиться Николай Лорер. Не любивший Майбороду после «истории» в Московском полку, он поведал о случившемся командиру вятцев. Но ни предостережения Лорера, ни тот хорошо известный полковому командиру факт, что за 10 лет службы капитан переменил уже шесть полков, не остановили Пестеля. Занимавшийся поиском источников финансирования своего предприятия, южный лидер остро нуждался в помощнике. Помощнике, который, будучи членом тайного общества, не был бы воплощением рыцарства и романтической честности. Сам же майор Лорер, человек глубоко нравственный и прямолинейный (его фамилия не фигурирует ни в одном из документов финансового следствия в Вятском полку), для этой роли явно не годился.
Видимо, прежде чем принять Майбороду в тайное общество, Пестель устроил ему — в январе 1824 года — серьезную проверку. Именно Майборода, по приказу полковника, стал движущей силой известной истории с солдатскими крагами. Майборода первым предложил солдатам своей роты «довольствоваться» сорока копейками за пару краг вместо положенных двух с половиной рублей. Когда же 1-я гренадерская рота на это согласилась, капитан лично уговорил всех других ротных командиров последовать его примеру — этот факт стал известен следователям из показаний штабс-капитанов Дукшинского и Урбанского, командовавших в 1824 году соответственно 3-й и 6-й мушкетерскими ротами Вятского полка.
И только после того, как капитан блестяще справился с возложенным на него поручением, он был принят Пестелем в тайное общество, стал соратником своего командира. Причем полковник искренне полюбил капитана: об этом свидетельствует, в частности, составленное Пестелем в конце 1824-го — начале 1825 года завещание. В завещании часть своих личных вещей он оставлял Майбороде.
Впоследствии в своем знаменитом доносе на высочайшее имя Майборода утверждал, что «слишком уж год», как он заметил в своем полковом командире «наклонность к нарушению всеобщего спокойствия». И вступил в заговор только для того, чтобы выведать планы нарушителя и сообщить о них правительству. Утверждения эти — сознательная ложь. Показания членов Южного общества рисуют капитана ревностным заговорщиком, искренне преданным своему начальнику по заговору. Он, например, помогал Пестелю наблюдать за настроениями офицеров в полку, изобретал пути добычи денег для «общего дела» и даже привез своему шефу из Тулы духовое ружье, которое Пестель планировал пустить в ход в случае начала революции. По словам командира Вятского полка, Майборода всегда оказывал ему «большую преданность».
Другую версию причин доноса Майбороды излагают многочисленные мемуаристы. Так, например, Басаргин замечает: «В 1825 году он (Майборода. —
Мемуаристам вторят историки: по их мнению, мотивами, побудившими Майбороду сделать донос, были «невозможность отчитаться в истраченных казенных деньгах» и «опасение быть преданным суду за злоупотребления в бытность приемщиком вещей от Вятского полка из комиссии Московского комиссариатского депо, о которых узнал Пестель».