En ny festning ved Flekkerøy havn
Arbeidet med festningsverket på Fredriksholm startet opp i 1655. Festningen stod ferdig i 1658 med et Øvre og Nedre verk. Øvre verk bestod av en gråsteinsmur med vollgang bak, og omkranset øyas høyere, østre del. Her stod et tårn, som huset kommandanten, samt tre kanonbatterier. Innenfor murene i Øvre verk lå to bygninger bygget i gråsteinsmur og bindingsverk, samt to kruttkjellere. Nedre verks gråsteinsmur omsluttet Øvre verk og størstedelen av øya, og inneholdt også tre kanonbatterier. Innenfor nedre verk stod det i 1750, i tillegg til en nybygget kommandantbolig i tre, minst fem mindre bygninger i mur og tre. Disse huset blant annet proviant, krutt, bakeri og soldater.
Forfall og gjenoppbygging
Fredriksholm ble ressursmessig nedprioritert mot slutten av 1700-tallet og til sist nedlagt i 1801. Da Danmark-Norge få år seinere kom i krig med England og Sverige, var Fredriksholm ubemannet. Den engelske blokaden av norskekysten begynte i 1807 og samme år gikk engelskmennene i land på Fredriksholm, sprengte gråsteinsmurene delvis i stykker og brant ned alt av treverk. Episoden førte få måneder seinere til vedtak om å befeste Vestergabet på nytt. Dette skjedde først ved oppsettingen av fastlandsbatteriet på Møvig i 1808-1809, i dag kjent som Batteriodden. Fredriksholm var også med i planene og byggingen av det festningsverket vi i dag kjenner på øya startet opp like etterpå. Det gamle Fredriksholm var før gjenoppbyggingen et sørgelig syn. Ikke bare var det herjet av engelskmennene, men ved byggingen av verftsmuren til Kongens verft i Kristiansand hadde det også blitt hentet stein fra de ødelagte murene på festningen.
Restene av de gamle murene ble nå fjernet, og terrenget planert ut, før en ny, tre til fem meter tykk mur av gråstein kledd med torv øverst, ble reist rundt holmen. Holmens høyeste, østligste punkt ble forsynt med en indre mur. Inne i fortet ble det anlagt flere bygninger, blant annet kaserner, vaktlokale og to hvelvede gråsteinskjellere for ammunisjon. Anlegget stod ferdig i 1813, med ni 18-punds kanoner. På 1850-tallet, under Krimkrigen, ble det reist tvil om Fredriksholm festnings militære verdi. For å kunne møte fienden lenger ute i Vestergabet ble fastlandsbatteriet på Batteriodden nå nedlagt og et jordbatteri satt opp på Gammeløya. Dette var underlagt kommandanten på Fredriksholm. Disse festningsverkene utgjorde forsvaret av Vestergabet og Indre Flekkerøy havn til de begge ble nedlagt i 1874. Bygningene på Fredriksholm ble revet i 1876 og materialene anvendt til oppføring av ny garnisonsskole i Kristiansand.