Ligesom i resten af Vendsyssel har Indre Mission, baptister og metodister siden slutningen af 1800-tallet stået stærkt i det nuværende kommuneområde. Især for Indre Mission var området en højborg, og den store Frederikshavn Kirke (indviet 1892) kan både ses som et udtryk for byens vækst på dette tidspunkt og for den stærke indremissionske vækkelse. I Skagen blev et missionshus indviet allerede i 1884, og frem til 1958 havde Indre Mission sin egen repræsentation i byrådet. I Sæby fik den indremissionske vækkelse fodfæste i 1872, og den slog for alvor igennem, da Sæby Kirke i 1882 fik C. Asschenfeldt-Hansen som præst. Hans forkyndelse var så stærk, at den trak kirkegængere til fra nabosognene, fx fiskerlejet Bangsbostrand. Netop i Bangsbostrand blev der fra 1901 drevet en brugs på religiøst grundlag, og her var det således ikke muligt at købe noget, der var stærkere end lyst øl. Den blev kaldt »Vorherres Bette Brugs« og var i drift indtil 1983.
Fra midten af 1950’erne begyndte det at gå tilbage for den indremissionske bevægelse, som dog fortsat er relativt aktiv både i de store og små byer. I Sæby har der været tradition for et omfattende arbejde med børn og unge i søndagsskoler gennem KFUM og KFUK samt FDF. I 1977 begyndte Indre Missions Samfund i Sæby at arrangere bibelcamping, som tiltrak troende fra hele landet indtil 2011, hvor arrangementet flyttede til Hjallerup pga. pladsproblemer. På baggrund af uenighed om linjen i folkekirken blev Vendsyssel Frimenighed i Strandby, der har tilknytning til Indre Mission, oprettet i 2012. Som noget særligt er menigheden åben over for de medlemmer af Indre Mission, som har valgt ikke længere at være medlemmer af folkekirken. Der er dog fortsat stor opbakning til folkekirken i kommunen, hvor 87 % er medlemmer mod 76,8 % på landsplan.
Baptisterne og metodisterne har været til stede i Frederikshavn siden hhv. 1860’erne og 1870’erne. Baptisterne har i dag menighed og kirke i Frederikshavn (indviet 1896), Skagen (opført 1939) og Sæby (oprindelig kirke indviet 1896, ny kirke 1940) samt menighedshus i Jerup. Baptistmenigheden i Tårs-Østervrå solgte i 2008 Østervrå Baptistkirke for i 2014 at indvie en ny kirke og et nyt kulturhus i Sæsing: Kirken i Kulturcenter Vendsyssel. Metodisterne har kirke i Frederikshavn (opført 1881) og Strandby (oprindelig kirke indviet 1928, ny kirke 1961). Menigheden i Strandby er landets største, og foreningslivet i byen præges fortsat af den store tilstedeværelse af både Indre Mission og Metodistkirken.
Udenlandske søfolk og fiskere har gennem mange år præget det religiøse liv i Frederikshavn Kommunes kystbyer, og i nyere tid har flygtninge og immigranter betydet tilførsel af nye trossamfund samt en forskydning af de eksisterende. Her kan nævnes Den Svenske Sømandskirke i Skagen (indviet 1925), baptistmenigheden Chin Church (stiftet af burmesiske flygtninge), som købte Sæby Baptistkirke i 2015, det muslimske Bosnjacki Kultur Center ejet af den bosniske forening i Frederikshavn (indviet 2014) samt den katolske Helligåndskirken Frederikshavn (indviet 1966). Sidstnævnte er tilknyttet Kamillianerordenen i Aalborg og har siden 2014 haft en tamilsk præst ansat til at varetage arbejdet med den tamilske menighed.
