Бєльовська фортеця заснована, як десята фортеця у складі Української лінії оборонних зміцнень в 1731 році, що проходила на сучасних територіях Харківської та Дніпропетровської області. Українська оборонна лінія була збудована за наказом Імператриці Анни Іоанівни. Бєльовська фортеця стала першою спорудою прийдешнього міста. Фортецю була закладена 11 серпня 1731 року, завершилось будівництво 20 жовтня 1733 року. Свою назву фортеця отримала від ландміліціонерів які прибули її охороняти, а точніше від міста звідки вони прибули Бєльовсь. З часом навколо Бєльовської фортеці розрослось містечко, яке у народі мало назву містечко при Бєльовській фортеці.
Імператорським указом від 14 лютого 1775 року було створено Азовську губернію у складі Катерининської і Бахмутської провінцій із центром у місті-фортеці Бєльовська. Катерининську провінцію було розширено землями Азова і Таганрога, Війська Донського та Дніпровської лінії, Кінбурна із землями між Бугом і Дніпром. Бахмутська провінція складалася з Бахмутського повіту і Слов’яносербії. Проведена ревізія 1775 року чоловічого населення Катерининської провінції у віці від 17 років зареєструвала 64 503 осіб. На запорізьких землях, включених до складу в Азовській губернії, було обліковано 36 574 чоловік: 21 728 чоловіків і 14 846 жінок. Населення проживало в 27 хуторах і 833 зимівниках.
У 1784 року повз містечко при Бєльовській фортеці проїздила Імператриця Катерина Велика за легендою вона зупинилась у місті та саме в цей час дізнається про народження свого онука Костянтина. За наказом Імператриці містечку надано статус міста та названий на честь онука Костянтиноградом.
Синагога зруйнована у роки окупації міста
На середину XIX століття в Костянтинограді проживало 2289 душ, було 2 кам’яні храми, 4 цегляні будинки й 326 дерев’яних. 1842 року для міста було затверджено герб: на зеленому щиті — план Бєльовської фортеці, під ним — постать воїна з кривою шаблею.
На кінець ХІХст. в місті проживало 3258 осіб (1696 чоловічої статі та 1562 — жіночої), налічувалося 935 дворових господарств, були 3 православні церкви, лютерано-німецька кірха, синагога, лікарня, повітове, парафійна та німецька школи, поштова станція, налічувалось 27 промислових підприємств, відбувалося 5 ярмарків на рік, були базари.
26 березня 1923 року Полтавський губернський виконком «засвідчив» постанову Костянтиноградського повітового виконкому від грудня 1922-го року перейменувати на знак нагородження орденом Трудового Червоного Прапора УСРР місто й повіт на Красноград і Красноградський. У 1923—1932 рр. разом з назвою Красноград вживали й української відміни Червоноград.
12 квітня 1923 р. ВУЦВК затвердив поділ Української СРР на 53 округи та 706 районів. Створена 7 березня 1923 року в Полтавській губернії Красногра́дська (іноді ще Червоногра́дська) окру́га займала 1113 квадратних верств (1266,66 км2) з населенням 49 048 осіб. Красноградську округу ліквідовано 15 червня 1925 постановою ВУЦВК від 3 червня 1925 року.
З 1922 року місто перейменоване на Красноград, однак ще до 1964 року залізнична станція називалася Костянтиноград.
9 лютого 1932 р. ВУЦВК затвердив постанову створити в УСРР п’ять областей: Харківську, Вінницьку, Київську, Одеську та Дніпропетровської. Землі колишньої Полтавської губернії розділили між Харківською, Дніпропетровською та Київською областями. Красноградський район відійшов до Харківської.
Під час організованого радянською владою Голодомору 1932—1933 років померло щонайменше 1062 жителі міста.
Нацистські війська вступили до міста 7 жовтня 1941 року. Радянські частини вибили нацистські війська з Краснограда 19 вересня 1943 року.
