I sommeren 1684 begyndte hammerslagene at lyde på Ertholmene. Fæstningsbyggeriet blev påbegyndt. Fæstningen Christiansø blev grundlagt som følge af en sømilitær oprustning i den sydlige Østersø. Danmarks sikkerhedssituation var særdeles alvorlig, for arvefjenden Sverige var blevet en europæisk stormagt, og Danmark havde med tabet af Skåne, Halland, Blekinge og Bornholm i 1658 med et pennestrøg mistet alle sine havne øst for Køge. En vellykket bornholmsk opstand mod det svenske herredømme gjorde dog kort efter atter Bornholm og Ertholmene danske.
Samtidig etablerede svenskerne den enorme flådebase Karlskrona i det tidligere danske område Blekinge. Fra Karlskrona kunne den svenske flåde stå til søs tidligere på året og være på havet i en længere periode, fordi denne flådebases sydlige beliggenhed bevirkede, at den var isfri i en længere periode end den nordligere flådehavn i Stockholm, hvor den svenske flåde hidtil havde haft sin hovedbase. Det danske søherredømme i den sydlige del af Østersøen var dermed truet, og som modsvar vendte Christian V og den danske statsadministration opmærksomheden mod Ertholmene og øgruppens naturlig havn. De rå skær blev betvunget, og fæstningen Christiansø blev grundlagt – muligvis verdens første fremskudte flådebase.
288 nordmænd blev sendt til klippeøen under ledelse af den hollandske fæstningsingeniør Anthony Coucheron, som havde erfaring fra Norge med fæstningsbyggeri på klippegrund. Granitten til tårne og batterier blev brudt på stedet. Alle andre byggematerialer måtte fragtes over havet, og fra Bornholm så man Ertholmenes konturer ændre sig.
Anthony Coucheron, som har bygget flere af de store fæstninger i Norge, er især kendt for sine fæstningstårne, hvoraf Store Tårn og Lille Tårn hører til blandt de største. Ideen til disse særegne tårne (som senere er blevet kaldt Martellotårne) fik Coucheron fra Middelhavet, hvor tårntypen var almindelig.
De første år var en kamp mod naturen – og vel også hinanden, i og med at der et par gange var optræk til mytteri.
Gyldenløves Batteri
Gyldenløves Batteri blev bygget i sommeren 1684 og er fæstningens første bygningsværk. Batteriet er et af de fire havnebatterier (foruden Juels, Spanns og Sehesteds Batterier), som skulle forsvare havneindløbet mod en invaderende flåde. En af Christiansøs befæstningsmæssige svagheder var nemlig, at en fjende i princippet kunne omgå øernes mange kanonbatterier og fæstningstårne ved at sejle direkte gennem havneindløbet, ind i fæstningens hjerte. Derfor var havnen i krigstid spærret af kabler og kæder. Neden for Gyldenløves Batteri kan I se et hul i muren, hvorigennem havnespærringen var fastgjort.
Gyldenløves Batteri er i øvrigt blevet forstærket og udbygget flere gange gennem århundrederne, hvilket I også kan se i de forskelligartede stenlag på batteriet.
Jomfrugalgen
Terrænet foran den store mur mellem Bielkes Port og Hofmanns Port kaldes Jomfrugalgen. Da den store mur blev bygget i starten af 1800-tallet, blev klippeformationerne, hvor muren nu står, sprængt til uigenkendelighed, Før bortsprængningen fandtes her en dyb kløft, man kan stadig få en fornemmelse af det i dag. Stedet kaldes Jomfrugalgen. Navnet stammer fra før 1684, hvor fæstningen blev anlagt. I den dybe kløft, fortælles det nemlig, at der blev fundet en galge, hvori der hang et lig af en kvinde, som skal være blevet hængt af sørøvere.