Войска тронулись к переправам через Терек 9-го апреля 1796 года. 3-й и 4-й батальоны Кубанского корпуса перешли его по понтонному мосту при Каргалинской станице и вместе с прочими войсками расположились лагерем на р. Каргине. Всего здесь собрано было 12 323 человека, причем в 2-х батальонах егерей состояло на лицо 1 321 чел., а в 6-ти батальонах мушкетер и гренадер 4 869 человек. Во всех войсках, включая отряд Савельева и десант, у графа Зубова было не более 18 000, вместо предположенных 30 000. Подкрепление должен был привести князь Цицианов. На скорое прибытие их не было надежды. Граф Зубов должен был торопиться походом до наступления знойного времени. Войска каспийского корпуса образовали четыре бригады — две пехотных и две конных, приблизительно по 2 500 человек в каждой. Иррегулярные же войска (до 2 000) составили резерв. Кубанские егеря и Кавказские гренадеры составили 1-ю бригаду под начальством генерал-майора Булгакова. Служебный порядок на походе предписано наблюдать по инструкции графа Румянцева.
После переправы через Сулак у Казиюрта (20-го—22-го апреля) корпус прибыл в Тарки, откуда следовал большей частью в одной колонне, испытывая большие трудности, двигаясь по карнизам отвесных скал и ущельям: солдаты, выпрягая лошадей и волов, перетаскивали орудия и повозки на себе, то спуская, то поднимая их в гору.
От реки Хамри-Озени, при урочище Тюпсис, Булгаков со своею бригадою, усиленной двумя ротами гренадер Владимирского мушкетерского полка, 14-ю эскадронами драгун астраханских и таганрогских, командами казаков, с шестью полевыми орудиями полевой артиллерии, должен был следовать в обход Дербента через Табасаранский перевал. Обход надлежало совершить в три дня и, не позже 2-го мая, Булгаков должен был обложить город с южной стороны; главные силы корпуса в это время должны были атаковать Дербент с севера.
Шейх-Али-хан Дербентский, собрав в крепости до 10 000 войск, в составе которых было немалое число лезгин, и ожидая подкрепления от разных ханов и владетелей Дагестана, полагал обороняться до последней крайности. При таких условиях, обходное движение отряда Булгакова приобретало особенное значение; от успеха его зависело овладение Дербентом.
Войскам Булгакова предстояло пройти для обхода не более 87-ми верст, но из них 20 верст «самыми труднейшими дефилеями» через Табасаранский хребет, верхняя часть которого покрыта дремучим лесом. Обе покатости чрезвычайно круты, имеют множество каменистых, утесистых стремнин.
Булгаков, выступив 29-го апреля из лагеря на р. Хамри-Озени, на другой день, не доходя 18-ти верст до Дербента, свернул на запад и к вечеру приблизился к началу Табасаранского дефиле; здесь он расположился лагерем. Подъем на главный хребет, или Бент, на протяжения трех верст представлял такие затруднения, что до полудня 1-го мая могли подняться только казаки и один егерский батальон. Остальные войска помогали подниматься артиллерии и обозу: дорога на глинистом грунте от шедшего дождя до того испортилась, что нужно было пособие не менее 200 человек, чтобы подвинуть с места 12-ти-фунтовый единорог. Но этот подъем артиллерии и повозок на Бент продолжался почти до полудня 2-го мая.
Не меньше затруднений отряд испытывал при спуске по ущелью на протяжении 14-ти верст: тут по косогору проходила столь узкая дорога, что по ней только два драгуна могли ехать рядом. Вправо от нее стремнина сажен на 100 глубины, а влево перпендикулярная стена в 80 сажен. С вершины горы нависшие камни, казалось, готовы были скатиться каждую минуту и задавить прохожего. Одна изломанная повозка останавливала движение всей колонны. Едва ночью 2-го мая егерские батальоны и казаки прибыли в долину, где начинались владения Дербентского хана. Когда люди улеглись на биваке, то проливной дождь произвел такое наводнение в узкой долине, что им пришлось провести всю ночь, стоя в воде, не смыкая глаз. Ясное утро осушило и обогрело солдат. Булгаков с отрядом, оттеснив передовыми войсками мелкие партии неприятельской конницы, подошел к Дербенту едва в час пополуночи 4-го мая и расположился с южной стороны крепости в ханских садах против предместья Дубари, примыкая правым флангом к морю, а левым—протянулся к горам, для чего рассыпаны были егеря 3-го батальона, вошедшие в связь с войсками главного корпуса.
Овладение Дербентом, в котором приняли участие егеря 3-го и 4-го батальонов Кубанского корпуса, действовавшие из траншей против замка Нарын-кале (на западной оконечности крепости), не потребовало больших усилий, когда 7-го мая удалось войскам главного корпуса овладеть передовою башнею. Батареи, построенные в траншеях в 40 саженях от замка Нарын-кале, своим огнем произвели обвал 10-го мая, и в тот-же вечер растворились настежь ворота, через которые хлынула толпа жителей в сопровождении 120-ти-летнего старца, имевшего в своих руках серебряные ключи Дербента, того самого старца, который за 74 года перед сим подносил ключи императору Петру Великому. Главнокомандующий вступил в город торжественно 13-го мая и занял все посты войсками отряда Савельева.