Паскевич, пытаясь выманить из Чечни главного руководителя чеченских повстанцев, в продолжение всего 1828 года через посредников предлагает Бейбулату вернуться на «русскую службу». Ему обещают капитанский чин, прощение и почести. Однако настойчивость, с какой делались эти предложения, показалась Бейбулату подозрительной. И потому переговоры он проводит через шамхала Тарковского Мехти, имеющего звание царского генерала. Бейбулат ведет переговоры о союзе с шамхальством, что заставляет шамхала, желающего, с одной стороны, преподнести русскому командованию сюрприз, а с другой — приобрести себе новых подданных и огромный доход, утаивать эти переговоры от Паскевича.
6 марта 1829 года Бейбулат со старшинами Чечни прибывает в Тарки. Чеченские старшины, принимая номинальное «подданство» шамхалу, пытались избежать подчинения царским приставам, отвести от Чечни угрозу постоянных набегов, получить льготы подданных шамхальства, оставаясь фактически самоуправляемыми и выплачивая шамхалу необременительную подать с каждого селения. Чеченские старшины требуют также от шамхала какой-либо гарантии, что Бейбулат не будет преследоваться царским командованием. Шамхал Тарковский охотно соглашается выдать в виде заложника чеченским старшинам своего сына, причем о последнем своем шаге согласия царского командования он не спрашивал. Окрыленный успехом, шамхал уведомляет командующего Кавказской армией Паскевича: «Спешу сообщить приятное известие: прибыли ко мне в Тарку из Чечни начальники чеченцев числом в 120 человек. Бейбулат, главный из них начальник, поручил мне сына своего аманатом, а я поручаю ему взять в Чечню сына моего Шахбаза... Надеюсь, что после сего жители Кавказа будут жить спокойно».
Чеченские старшины увезли с собой в глубь страны сына шамхала, а ловкий и блестящий дипломат Бейбулат со своим новым союзником шамхалом Тарковским отправляется к русскому командованию. Царское командование пытается арестовать Бейбулата, но возмущенный шамхал заявил, что, во-первых, он дал чеченским старшинам слово, что с Бейбулатом ничего не случится, и, во-вторых, за Бейбулата в заложники отдан его сын. При этом шамхал недвусмысленно высказался, что всякое действие, направленное против Бейбулата, есть действие, направленное против него, и он в таком случае ни с чем считаться не будет.
Царское командование серьезно разгневалось на шамхала, но опасаясь его влияния в волнующемся Дагестане, вынуждено было смириться. Графу Паскевичу пришел из Петербурга строгий приказ с выговором, в котором указывалось, что русское командование уронило честь империи своей политикой, выдав в аманаты сына владетельного князя шамхала Тарковского.
Бейбулат же в совершенной безопасности, подтрунивая над своими новыми «союзниками», находится в русском лагере. Теперь в отношении его царское командование ведет иную политику. Оно уже не требует, чтобы он давал сведения о действиях горцев. Оно хочет лишь одного — чтобы он был подальше от Чечни. С этой целью Паскевич пишет, чтобы Бейбулат Таймиев был направлен к нему в Тифлис.
Приехав в Тифлис, Бейбулат узнает, что Паскевич находится в действующих войсках. Поняв, что его обманули, он пытается немедленно возвратиться в Чечню, но его силой задерживают в Тифлисе.
Вскоре Паскевич дает разрешение на приезд Бейбулата в действующую армию. Пала турецкая крепость Арзрум. 7 июля 1829 года по случаю ее взятия был устроен парад. Состоявший в конвое главнокомандующего «разбойник» и «атаман Чечни» Бейбулат с тридцатью чеченцами также принял участие в параде войск, заняв самое почетное место. Военный писатель штаб-офицер Кавказского корпуса, полковой командир действующей армии подполковник И. Т. Радожицкий в своем повествовании «Походные записки артиллериста в Азии с 1829 по 1831 год» писал: «В парадном каре я нарочно ездил смотреть Бейбулата, который со своими чеченцами (их было 30 всадников) стоял верхом на правом фланге сводно-линейного казачьего полка... Это человек среднего роста, довольно толстый, пожилой, с багровым лицом и темно-красной круглой от ушей бородкой; глаза небольшие, быстрые. В физиономии нет ничего отличительного, кроме лукавства и скрытности...
