Аграханское казачье войско было образовано в конце царствования Петра I, который, прибыв в 1722 году на Терек, приказал выдвинуть российскую пограничную линию на реку Сулак. Здесь, на месте, где от Сулака отделяется рукав — Аграхань, была устроена крепость Святого Креста, a вблизи неё были поселены терские казаки, названные Аграханским войском. Ими образованы по течению Аграхани три станицы: Каменка, Прорва, Кузьминка.
Главным назначением войска было охрана прибрежья и сообщения с морем. В 1724 году казаки новообразованного войска были усилены 1 000 семьями донских казаков и местными инородцами. Однако обстоятельства не способствовали развитию Аграханского войска: постоянные набеги чеченцев и дагестанцев вынуждали казаков часто переселяться с места на место, a неблагоприятные климатические условия гибельно влияли на прирост казачьего населения, значительная часть которого вымерла.
Когда в 1732 и 1735 годах по мирным трактатам с Персией российская пограничная линия отодвинулась к Тереку и крепость Святого Креста была упразднена, a вместо неё был построен Кизляр, — то в округ последнего переведены были остатки Аграханского войска, причём из донцов образовалось Терско-Семейное войско, a из бывших терцев — Терско-Кизлярское войско. Первое из них выставляло до 400 служилых казаков, а второе — лишь около 200.