Село основано в конце XIX века (1897 г.). Новая Деревня расположена в 24 км к югу от районного центра на правом берегу Большого Зеленчука. Население на 1.01.1997 г. составляло 2,2 тыс. человек.

В междуречье Б. Зеленчука и Кубани возник целый ряд хуторов. Несколько из них принадлежали предпринимателю Мясникову. Среди последних и, так называемый, Верхнемясниковский хутор. Позже он стал называться Александро – Михайловским. А в 1927 году был переименован в Новую Деревню.

Хутор административно входил в состав Ивановской волости Баталпашинского отдела Кубанской области.

Согласно данным переписи 1897 г., в Александро – Михайловском хуторе в 18 хозяйствах оседло проживало 108 человек.

Жители занимались хлебопашеством и животноводством. А помимо этого – огородничеством, разведением садов. Целым состоянием были сотни десятин пойменных лесов.

Православное население хутора являлось прихожанами Рождество – Богородицкой церкви селения Ивановского.

В 1918 г. в Александро – Михайловском  была установлена советская власть. Был создан красногвардейский отряд. В ходе гражданской войны хутор несколько раз переходил из рук в руки. Здесь были Шкуро, Покровский, Филимонов, а так же Балахонов, Кочубей, Сорокин. С декабря 1918 по март 1920 хутор был под властью деникинцев.

В конце 20-х гг. в Александро – Михайловском, переименованном двадцати пяти тысячниками в Новую Деревню стали образовываться ТОЗы, КОВы, с/х артели. Одна треть хозяйства оставалась единоличной, но в период коллективизации они стали ликвидироваться. В 1930 г. в Новой Деревне образован колхоз "Запорожец” (предс. Нештарев). Обслуживался он тракторной бригадой Невинномысской МТС.

На 1940 год в Новой Деревне насчитывалось 446 семей. В них – 2240 членов колхоза. Построек – 508, из них кирпичных и каменных – 38, саманных – 190, турлучных – 111, деревянных – 49, комбинированных – 120.

На территории Новодеревенского сельсовета до войны, кроме 10 колхозов, было 3 копхоза "Донбасс”, "Маслодел”, "Птицевод”. Основная отрасль хозяйства животноводство.

В годы войны на фронт ушли 322 хуторянина междуречья. Более половины погибло.  Герой Советского Союза уроженец хутора – Лаптеа К. Я. В августе 1942 Новая Деревня была занята оккупационными частями. Здание школы стало местоприбыванием Междуреченской управы. Хутор освободили 21 января 1943 г. Новодеревенский сельсовет возобновил свою деятельность. Заработала школа.

После войны колхозы были укрепнены. Колхоз им. Лаптева влился в колхоз им. Молотова и "Кубань”. Через некоторое время хозяйства были реорганизованы в фермы крупнейшего в районе совхоза "Невинномысский”. В 1959 на базе ферм овцесовхоза и Красногвардейской птицефабрики "Невинномысская” был организован птице – овощеводческий совхоз "Междуреченский”. В настоящее время это СХП "Междуреченское”. В 60-е гг. из его состава выделились узкоспециализированные хозяйства – плодосовхоз "Западный” и птицефабрика "Нивинномысская”.

60 – 80-е годы – активного строительства. В 1967 г. в Новую Деревню был проведен газ. Возведены Дом Культуры, средняя школа, детсад, ясли, дом быта. В 1986 г. вступил в строй спортивный комплекс.

Село гордится земляками-художниками: Чубенко Н.И. и Бабич А.И. В 1998 году художник Чубенко Н.И. открыл первую в крае частную картинную галерею.

Созданнй в 1968 г. на базе плодоовощного совхоза "Междуреченского” племрепродуктор "Невинномысский”   в настоящее время являются в районе лидером по производству птицеводческой продукции. В 1995 г. АО "Междуреченское” 1350 га земли. Валовый сбор зерна составил 27253 цент. С каждого гектара АОПП "Невинномысское” вырастило 416 т. мяса всех видов. Автобусное сообщение связывает населенный пункт с районным центром.

В состав Новодеревенской сельской администрации входят также хутора: Воротниковский с населением на 1.01.97 г. 100 человек, Дегтяревский – 600 человек, Маковский – 100 человек, Новозеленчукский – 700 человек, Новокубанский – 200 человек, Новородниковский – 100 человек, Прогресс – 700 человек, Рабочий – 500 человек, Харьковский – 400 человек.

Авторы: Бочкарёва З.В., Котов С.Н. Опубликовано в издании "История городов и сёл Ставрополья" (2002, 2008).