Nowi władcy Krakowa już w 1798 roku zaczęli planować otoczenie świeżo zdobytego miasta całkowicie nowymi fortyfikacjami. Ta potrzeba nie została spełniona przez kolejne pół wieku, bo Kraków wyrywał się Habsburgom z rąk.
Najpierw w wyniku wojen napoleońskich z części zaboru pruskiego zostało utworzone Księstwo Warszawskie. Gdy Austriacy zaatakowali je w kwietniu 1809 roku, dowodzący polskimi wojskami książę Józef Poniatowski przeprowadził bardzo dobrą kampanię wojenną, 15 lipca 1809 roku wyzwalając Kraków bez walki. Po klęsce Napoleona w wyniku ustaleń w czasie Kongresu Wiedeńskiego w 1815 roku Kraków stał się Rzecząpospolitą Krakowską, ostatnim w miarę wolnym skrawkiem Rzeczypospolitej. Półniezależnego statusu miasta pilnowały trzy mocarstwa zaborcze, choć w rzeczywistości każde z nich chętnie włączyłoby Kraków i jego okolice do swoich włości. Umocnienia z czasów Kościuszki przydały się wówczas do określenia granic miasta, gdzie pobierano podatek od wwożonych do strefy bezcłowej towarów, głównie spożywczych. W tym czasie rządzący miastem senatorowie stwierdzili konieczność uporządkowania i upiększenia przestrzeni przez przeprowadzenie rozbiórki zniszczonych umocnień miejskich sprzed wieków, z których ocalał tylko północny fragment z Bramą Floriańską, trzema basztami i Barbakanem. Na miejscu dawnej fosy, murów i przedpola założono Plantacye, zwane obecnie Plantami. Tak powstało 21 hektarów parku miejskiego.
W 1846 roku, po klęsce powstania krakowskiego, Rzeczpospolita Krakowska została zlikwidowana i przyznana Austrii, która przystąpiła do zabezpieczenia swoich nowych terenów – Kraków stał się punktem o znaczeniu strategicznym dla ochrony zachodniej części Galicji przed ewentualnymi zakusami Prus i Rosji. Rozpoczęto rozbudowę umocnień od Wawelu, który sam stał się koszarami wojskowymi, oraz wokół miasta.
Oficjalna decyzja o budowie Twierdzy Kraków zapadła 12 kwietnia 1850 roku, gdy cesarz Franciszek Józef I podpisał stosowny dokument. Umocnione miasta Kraków i potem też Przemyśl mogły zabezpieczyć przed Prusami i Rosją nie tylko Galicję, ale i wnętrze habsburskiego imperium – Czechy, Morawy, Słowację i Węgry. Zgodnie z ówczesnymi najnowszymi trendami sztuki obronnej Krakowa miały bronić umocnienia zbudowane w systemie poligonalnym – rozproszone i wspomagające się nawzajem, ale nietworzące szczelnego i ciągłego pierścienia, jak niegdyś mury obronne. 25 maja 1856 roku Kraków został oficjalnie ogłoszony twierdzą. Przez kolejne ponad sześć dekad, niemalże do końca rządów coraz bardziej liberalnego w oczach polskich poddanych cesarza Austrii, a potem Austro-Węgier, trwała rozbudowa kolejnych linii umocnień wokół miasta. Z czasem stało się ono jedną z najpotężniejszych twierdz w Europie, tworząc największy zespół obronny na terenach polskich.
Miasta zaczęto fortyfikować jeszcze przed oficjalną decyzją cesarską. Na początek austriaccy wojskowi rozpoczęli rozbudowę umocnień Wawelu, który miał stać się cytadelą, co wkrótce i niespodziewanie przydało się do ujarzmienia zrewoltowanych mieszkańców w czasie Wiosny Ludów. Z nowo powstałych szańców w kwietniu 1848 roku Austriacy ostrzelali z armat Kraków – tylko dzięki szybkiej kapitulacji mieszkańców, która zakończyła ostrzał, i opadom deszczu, które ugasiły pożary, obyło się bez większej tragedii, choć od pocisków i odłamków zginęło 30 krakowian. Był to jedyny raz, gdy umocnienia przyszłej krakowskiej twierdzy posłużyły do spacyfikowania miasta, a nie jego obrony. Równocześnie kontynuowano budowę umocnień po stronie podgórskiej. Prace te nasilono po wydaniu decyzji o budowie twierdzy. Jako pierwsze powstały forty broniące obu miast: „Krakus”, „Św. Benedykt” i „Krzemionki” na południowym brzegu, oraz forty „Kościuszko”, „Luneta Warszawska” i „Luneta Grzegórzecka” na północnym.
Prace przyspieszono w czasie wojny krymskiej w latach 1853–1856, gdy relacje pomiędzy Austrią i Rosją popsuły się tak mocno, że pojawiła się realna obawa ataku wojsk carskich. Nowych fortów nie dało się jednak wybudować z dnia na dzień, więc miasto otoczono tym, co dało się szybko przygotować – 30 szańcami polowymi usypanymi z ziemi i wzmocnionymi drewnem dla piechoty i artylerii. Ostatecznie do wojny nie doszło, a z czasem niektóre szańce zaczęto przebudowywać na forty, zwane reditowymi – z charakterystyczną półokrągłą reditą, czyli podwyższonym miejscem do ustawiania armat i prowadzenia ognia.