Село Новокиевка образовалось в 1908 г. переселенцами из Киевской и Херсонской губерний, юридически оно зарегистрировано в 1913 г. в Славгородском уезде.
Каждой из переселившихся семей (всего их было 7) отвели отдельный участок исходя из количества душ в семье. Он выделялся с условием, что должен хорошо обрабатываться, за этим строго следил староста.
Первый Совет организовался в 1919 г., первая коммуна – в 1929 г., которая через год распалась. В сельский Совет входили села: Новокиевка, Преображенка, Романовка, Дмитриевка, Александровка, Петропавловка, Славянка, Табуны. Каждое из сел представляло собой колхоз. В 1950 г. все эти колхозы объединились в колхоз им. Я. М. Свердлова с центральной усадьбой в Новокиевке. В 1954 г. колхоз был реорганизован в совхоз, на базе которого образовались целинные совхозы «Алтай» и «Табунский».
С 1935 по 1938 гг. село Новокиевка было районным центром со средней школой, которая просуществовала до 1948 г., превратившись затем в семилетку.
В годы Великой Отечественной войны с фронта не вернулось 36 жителей села. В их память к 30-летию Победы был воздвигнут в селе обелиск, а в школе – создан зал Боевой Славы.
В 2018 г. в селе проживало 107 жителей. В 2020 г. численность населения составляла 92 чел.
Полеводством занимаются два крестьянско-фермерских хозяйства: В. В. Ветрова и А. И. Мартына. Разведением крупного рогатого скота и производством молока занимается КФХ Т. Гайслер.
В селе есть муниципальная школа основного общего образования. В 2019–2020 учебном году в ней обучалось 32 школьника.
