Через несколько времени, именно 25-го октября 1818 года, А. П., оставя в Грозной приличный гарнизон, повел отряд, в числе 5000 человек пехоты, казаков и артиллерии, под личным своим предводительством в Дагестан, для усмирения лезгин, взбунтовавшегося там против своего владетеля Шамхала Тарковского, всегда мирного и верного слуги Государю Императору и России. Шамхал имел чин нашего генерал-лейтенанта и проживал в своей резиденции, в городе Тарках, стоящем на горе, в пяти верстах от берега Каспийского моря. По прибытии нашего отряда в Тарки, наступил проливной дождь, который не переставал лить целую неделю, так что решительно препятствовал дальнейшему походу, и отряд испытал на деле пословицу: «сиди у моря да жди погоды». По грязной, гористой и незнакомой дороге тянулся транспорт с снарядами и провиантом и, терпя много бедствий от ненастной погоды, не мог прибыть к отряду вовремя, и наконец, 9-го ноября, в 25-ти верстах от г. Тарки решительно остановился, заметенный снегом, который в тот день буквально на аршин покрыл землю. В ночь на 10-е число об этом дано было знать главнокомандующему через одного туземца. Очищением дороге в Дагестане для удобного туземца. Очищением дороге в Дагестане для удобного проезда по горам артиллерии занимался я, и потому Алексей Петрович, потребовав меня к себе, приказал, с 400-ми жителей города, прочищать всю дорогу от снега навстречу транспорту, начиная от Тарков. Я взял с собой в проводники того самого туземца, который привез неприятное известие об остановке транспорта, и с толпою туземцев, снабженных набранными в городе кое-какими лопатами, около полудня принялся за исполнение приказания главнокомандующего.

В июне месяце 1819 года главнокомандующий, желая окончательно восстановить покорность в Дагестане, под личным своим предводительством вторично собрал прошлогодний отряд, усиленный Куринским и 8-м Егерским полками. По трудному пути, преодолевая все преграды, отряд добрался до деревни Андреевской, в которую русская нога до тех пор не вступала повелительницей. 18-го июня 1819 года на горе близ этой деревни заложена крепость, с блокгаузами, которую Алексей Петрович назвал «Внезапная». Стены крепости были возведены из сырого кирпича, руками солдат; они же приготовляли и самый кирпич из глины, смешанной с соломенною трухою или, как туземцы называют, с саманом.

Во время постройки крепости Внезапной наш отряд окружала цепь рядовых, а ночью выставляясь и другая цепь, называемая секретною, в которой часовые стояли друг от друга в 20-ти саженях и потом ложились на землю по два в ряд. Это правило осторожности соблюдалось во все время похода и при каждой дневке. В отряде, как выше сказано, находился 8-й Егерский полк, состоявший большею частью из молодых солдат. Этим полком командовал бывший адъютант графа Ланжерона в 1812 году полковник Шульц, молодой, образованный и красивый воин, всеми любимый и уважаемый. Он следовал с полком. Не доходя Андреевской деревни за 40 или 50 верст, Алексей Петрович, изыскивая местность, удобную для постройки на ней крепости, остановил отряд на дневку и, зная молодость солдат 8-го Егерского полка, поехал ночью осмотреть, исправно ли размещена цепь. Заметив, что некоторые солдаты в секретной цепи спят, он пригласил к себе утром рано командира полка Шульца и сделал ему замечание насчет сопливости его солдат. Это замечание сильно подействовало на самолюбие Шульца, и он на другую ночь, пред выступлением отряда после дневки, лично поехал осматривать секретную цепь, взяв с собою батальонного командира майора Ганемана. Едучи верхом перед цепью, они разговаривали между собою по-немецки. Лежащий в секрете рядовой его полка, малороссиянин Яценко, предполагая в темноте, что едут неприятели, сделал из ружья выстрел, которым ранил в пах своего полкового командира. По сделанному выстрелу отряд встрепенулся и закричали «к ружью!» В мгновение ока отряд двинулся к цепи по направлению к выстрелу. Майор Ганеман тут же донес Алексею Петровичу о случившемся, и раненого Шульца, по приказанию Алексея Петровича.