It is unclear how the first Cossack community appeared on the Terek. One theory is that they were descendants of the Khazar state and of the Tmutarakan Principality, as there are records indicating that Mstislav of Tmutarakan in the Battle of Listveno in 1023 had Cossacks on his side when he destroyed the army of Yaroslav the Wise. This would mean the Slavic peoples of the Caucasus are native to the region having settled there much earlier.(?) But later Terek Cossacks assimilated the first Terek Cossacks and introduced their own new agriculture.
The earliest known records of Slavic settlements on the lower Terek River date to 1520 when the Ryazan Principality was annexed by the Grand Duchy of Moscow and a lone group left and settled in the natural haven of the Terek River (modern northern Chechnya). The early settlement was located at the mouth of the Aktash River. This formed the oldest Cossack group, the Greben Cossacks (Гребенские казаки Grebenskiye Kazaki) who settled on both banks of the river.
In 1559-71 the Tsardom of Russia, in the course of several campaigns, built several fortifications, during which the first Terka was built, later taken over by the still independent Cossacks. In 1577, after the Volga Cossacks were defeated by the strelets
Ivan Murashkin, many scattered, some of whom settled in the Terek basin and Voevoda Novosiltsev built the second Terka on the Terek, marking the start of the Terek Cossacks. In 1584 this Terka was again taken over by Cossacks, some of whom were recruited by the Georgian king Simon I of Kartli.
In a separate story, an ataman of the Don Cossack Host named Andrei Shadrin led a band of three Cossack sotnias to the Kumyk lands, founding a frontier town called 'Tersky' (location uncertain). This may have been partially motivated by his tense relations with Yermak Timofeyevich. He subsequently founded Andreyevo (the modern Endirey), which was said to be named for him.
In the late 16th century several campaigns by the Terek Cossacks were carried out against the Ottoman Empire (Temryuk) which led the Sultan to complain to Ivan the Terrible. In 1589 the first outpost on the Sunzha was built and a permanent Terka, later known as Tersky Gorodok, was built on the lower Terek.