Станица основана в 1769 году на юге района, на левом крутом берегу Терека. История возникновения станицы тесно связана со стремлением русского правительства закрепиться на Северном Кавказе. 2 июля 1765 г. Поступил указ на имя графа Панина о поселении между Моздоком и Кизляром 517 семей с Волги. Они образовали ряд станиц, в том числе и Стодеревскую. Так же Стодеревскую основывали семьи казаков с Дона, самыми же первыми посленцами были калмыки, которые ушли через некоторое время после основания поселения.

В 1832 г. Количество домов – 157, в которых проживало 494 мужчин и 468 женщин.

По поводу названия есть несколько версий: одна из них связана с фамилией новоселов Стодеревцевых, вторая — с якобы существовавшим распоряжением Моздокского отдела о вырубке ста деревьев

Также есть версия, согласно которой люди прибывшие основывать поселение сложили православную часовню из ста деревьев. Наиболее вероятно, что эта часовня простояла до революции, после чего сгорела либо была сожжена революционными комиссарами. По мнению одного из старожилов, эта версия не верна, так как до революции в Стодеревской стояла кирпичная большая церковь на берегу Терека (в народе это место называется «Крутые»), разрушенная авиабомбой во время Второй мировой войны. Уже после войны стены были окончательно снесены