Гребенские казаки являлись одной из старейших казацких общин — время её возникновения 1-я половина XVI века, либо, возможно даже конец XV века. Историк Болтин считал, что они пошли от Пятигорских Казаков или Черкасов. В 1380 году после битвы на Куликовом Поле гребенские казаки поднесли Московскому князю Дмитрию Донскому икону, принесенную ими с гор в которых они проживали (Гребневская Божия Матерь). Эти свидетельства дают основание для утверждения, что Гребенские казаки- Казаровцы, находились на Северном Кавказе уже во время Хазарской империи.
Предположения откуда пошли гребенские казаки высказываются разные; это возможно рязанские казаки, не пожелавшие в свое время идти под руку Москвы, и бежавшие крестьяне и донские казаки в предгорье Кавказа, и волжские вольные казаки ушедшие после их разгрома на Волге царскими войсками, и потомки хазар (по версии Гумилева). Губарев Г.В. вообще относит гребенских казаков к скифам. Версий много и видимо истину мы не узнаем никогда.
Почему назывались "гребенские", существует так же несколько версий. По одной из них так называли казаков, которые селились за горными гребнями в урочище Гребни.
Постепенно казаки из урочища Гребни расселились вдоль реки Сунжи, по среднему и нижнему Тереку. Однако в 1685 году, под давлением часто нападавших горских народов, гребенским казакам пришлось оставить предгорья и поселиться ближе к Тереку, на его правом берегу. По мнению некоторых историков гребенские казаки начали служить России еще во времена Ивана Грозного с 1577 года.
В 1711 году гребенские казаки переселились с правого берега Терека на левый. В течение XVII века гребенские казаки вели борьбу против Шамхала Тарковского, с ногайскими и крымскими татарами, самостоятельно или под началом Москвы. В ходе Русско-турецкой войны 1686—1700 годов гребенские казаки были привлечены в состав русского войска: они принимали участие во вторжении на территорию Крымского ханства, в Крымских походах 1687 и 1689 годов, в Азовских походах Петра I в 1695 и 1696 годах. В 1711 году, когда царь Петр двигался к Пруту, а граф Апраксин организовал поход против Кубанских татар и нанес им поражение, с помощью кабардинцев и гребенских казаков. При этом он уговорил казаков перейти на левый берег Терека и образовал линию, которая послужила связью между нижней Кабардой и городком Терком.
В 1712 году казаки перебрались на указанные места и поставили по левому берегу Терека 5 городков: Червленный, Щедринский, Новогладковский, Старогладковский, Курдюковский. После переселения гребенцов с правого берега Терека на левый, из них было сформировано Гребенское казачье войско. Гребенские казаки выставляли на службу не менее 1 тыс. человек. Половина из них состояла на жалованье и ходила в походы по требованиям правительства, а другая оставалась для охраны жилищ и без казенного содержания. Земельное владение казаков на левом берегу простиралось на 80 верст в длину и на 10-20 верст в ширину. Они занимались хлебопашеством, скотоводством, коневодством, виноделием, рыбным промыслом на Тереке и взморье, охотой и шелководством.
Петр I" указом 14 марта 1716 года повелел им выставить в состав 6-тыс. отряда, под нач. кн. А. Бековича-Черкасского 500 казаков". Они приняли участие в Хивинском походе, все кроме 2 человек, погибли. В этом походе войско лишилось более ; всех казаков. После такой потери гребенские казаки никогда уже не могли оправиться в численном отношении.
22 декабря 1720 года, согласно именному указу Петра I, Гребенское казачье войско было подчинено Астраханскому губернатору. Впоследствии по указу Петра I, все казаки и казачьи войска были подчинены высшему органу военного управления в Российской империи — Военной Коллегии. В 1724 году с Дона, на усиление Гребенского войска, было переселено 500 семей донских казаков. В 1746 году к Гребенскому войску казачьему было присоединено Терское Семейное казачье войско, но совместно они просуществовали недолго. В 1755 году из-за постоянных жалоб казаков этих войск на неправильное деление денежного и хлебного жалования, поступающее из казны(терские казаки получали жалование 12 рублей и овса 6 четвертей, а гребенские 10 рублей жалования и овса по 3 четверти), их опять разделили (гребенские казаки стали получать 12 рублей жалования и овса 6 четвертей). 26 сентября 1788 года войско отличилось в сражении на реке Убин в составе войск генерала Текелли, против турок и черкесов под предводительством паши Анжи-Мустафы. В 1791 году казаки принимали участие во взятии крепости Анапа.
К началу царствования Александра I гребенские казаки выставляли 466 казаков и 34 офицера. В 1819 году Гребенское войско получило полковое устройство (5 сотен, всего 700 казаков), но именовалось войском. В 1826—29 годах гребенские казаки принимали участие во всех войнах с Персией и с Турцией. В 1831 году участвовали в усмирении польского мятежа, высылая сотни в состав сводных линейных казачьих полков. В этом же году из гребенских казаков был сформирован конвой Николая I, в составе двух офицеров, четырех урядников и 24-ех казаков. В 1831 году все отдельные полки и войска, поселенные на Кавказе, были объединены в Кавказское линейное казачье войско. В 1845 году войско было переименовано в Гребенский казачий полк (6 сотенного состава, 20 офицеров и 861 казак), который, согласно положению о Кавказском линейном войске, вошел в состав 8-ой бригады.
За свою историю Гребенское войско получило свыше 120 различных наград; знамен, штандартов, знаков на головные уборы и других регалий. Так закончилась самостоятельная история Гребенского казачьего войска, которая продолжилась уже в составе Кавказского линейного и Терского казачьих войск.