Так начались его мытарства. Четыре года он «истлевал в гарнизоне» в этом азиатском захолустье, только литературным трудом и любовными приключениями преодолевая свою «хорьковую дремоту». Напрасно молил он о переводе в армию, сражавшуюся с горцами. Тогда враг, словно сжалившись над ним, сам пришел к нему. Кази-Мулла подступил к стенам Дербента и восемь дней осаждал его. Счастливый Бестужев писал своим братьям: «Я дышал эту осень своей атмосферой, я дышал дымом пороха, туманом гор. Я топтал снега Кавказа и сражался с сынами его — достойные враги… Бог, который выводил меня из челюстей львиных и прежде, не дал укусить меня ни одной свинцовой мухе… шинель моя пробита в двух местах». Рота присудила ему Георгиевский крест, но начальство ему креста не дало. Это был романтический эпизод, а потом снова потянулось «Бог знает что такое: смертью назвать грешно, а жизнью совестно». И в сердце, стойкое бестужевское сердце, где никогда не гасла веселая надежда: авось, счастье, случай, ловкость выведут снова на широкую дорогу, на вольную волю — в это сердце всё чаще закрадывалось сознанье, что жизнь кончена, что возврата не будет. «Неужели кровь моя стынет? Зачем же кипит еще мое сердце! В эту ночь я видел себя ребенком…» И Бестужев, рассказывая свой мрачный сон, с горестным удивлением отмечает, что отравлены даже его сны. Самый бодрый из декабристов видел, как медленно заливает его отчаянье. Жизнь его была в постоянной опасности от болезней — оспа, горячка, чума косили солдат. Его батальонный начальник ненавидел его — что само уже способно было превратить его жизнь в ад. Но он не сдавался, продолжал писать и писал лучше прежнего. Марлинский понемногу отделывался от своего несносного стиля. В его рассказах, наряду с романтическими горцами, появился простой русский солдат и правдиво зарисованный офицер. Но литература не давала ему полного удовлетворения; может быть, он, как критик, чувствовал слабость и преходящесть своих творений? Он писал: «для вольного разгула дарования надо простор… Когда вздумаю, что эта игра, или страдание души — и всё-таки поденщина для улучшения своего быта, — кисну, тяну, холодею, вяжу узлы как-нибудь». Трудно писать вдали от всякой литературной среды. Был еще один интерес в жизни — женщины. Он по прежнему жаждал «целой Африки любви». «Владею лучшей дамочкой из целого города — писал он, — сводить с ума женщин для меня не новинка. Итак, vogue la galère!» Галера шла в опасном фарватере: «Всегда рука на кинжале и ухо — на часах… и переодевания её, и прогулки и визиты ко мне… и удачные, забавные обманы аргусов… о, прелюбопытный роман вроде Фоблаза!»
Один эпизод закончился трагически. К нему приходила в гости простая девушка, унтер-офицерская дочь, Ольга Нестерцова (уж не она ли в бестужевском воображении превратилась в «лучшую дамочку в городе»?). В феврале 1836 года она была у него под вечер. Они о чём-то весело говорили, Бестужев хохотал, девушка прилегла на кровать, «резвилась» на ней. Под подушкой у Бестужева всегда лежал заряженный пистолет. По всей вероятности, Нестерцова задела курок, пистолет выстрелил и смертельно ранил ее. Перед смертью она успела сказать, что Бестужев в смерти её не виновен. Но вокруг него создалась атмосфера недружелюбия, его батальонный командир решительно оставался в убеждении, что Ольгу убил из ревности развратный штрафной, и даже по собственному почину нарядил следствие. Это лишило Бестужева заслуженной им боевой награды и производства в офицеры, которое одно могло принести избавление.