La fondazione del club risale al 1929, quando un gruppo di lavoratori del porto di Gdynia fondarono il Klub Sportowy Gdynia. Nel 1932, il nuovo stadio del Klub Sportowy fu aperto al Polanka Redlowska. Questo luogo è stato usato fino al 2000. Nel 1934 fu fondato il Klub Sportowy Kotwica ("club sportivo àncora"). Entrambe le squadre esistettero fino al 1939.
Nel 1949 fu fondato il Rybacki Klub Sportowy MIR ("club sportivo pescatori MIR"), che tre anni dopo cambiò nome in Klub Sportowy Kolejarz-Arka Gdynia.
Nel 1953 la squadra fu promossa per la prima volta nella terza divisione polacca di calcio. Nel 1960, dopo una partita combattuta contro l'Hutnik Kraków, l'Arka ottenne la promozione in seconda divisione.
Nel 1964 l'Arka si fuse con il Doker Gdynia per creare il Morski Związkowy Klub Sportowy MZKS Gdynia ("club sportivo marittimo unito MZKS Gdynia"). Nel 1972 il nome fu cambiato in Arka. Due anni dopo la squadra passò nella prima divisione polacca, l'attuale Ekstraklasa. Nel 1979 la squadra, allenata da Czesław Boguszewicz, divenne la prima compagine del Mar Baltico polacco a vincere la Coppa di Polonia.
Tra il 1980 e 1990 l'Arka militò tra la seconda e terza divisione. Nel 2001, dopo sei anni in terza divisione, ottenne la promozione nella seconda serie polacca e nel 2005 tornò in Ekstraklasa dopo ventitré anni di assenza.
Nel 2011 la città di Gdynia completò la costruzione del nuovo stadio, situato in via Olimpijska. Il 19 febbraio 2011 l'impianto fu inaugurato con un'amichevole finita 1-1 contro i bulgari del Beroe. Nello stesso anno la squadra retrocesse in seconda divisione.
Nel 2016, classificatasi prima nella seconda divisione, l'Arka passò in Ekstraklasa. Nel 2017 la squadra vinse la Coppa di Polonia per la seconda volta e nello stesso anno la Supercoppa di Polonia, vinta nuovamente nel 2018. Nel 2020 retrocesse nuovamente in seconda serie.
L'Arka è una delle squadre più tifate in Polonia, supportata soprattutto dalla Pomerania. Oltre al Trójmiasto, la tripla città, l'Arka vanta club di tifosi sparsi per tutte le maggiori città della regione, come ad esempio Tczew, Wejherowo, Braniewo e Kościerzyna. Altri sodalizi di sostenitori dell'Arka sono presenti in tutta la Polonia, come a Zakopane e Województwo lubelskie, e altri all'estero, in Germania, dove sono stati fondati dai tifosi dell'Arka espatriati a Oberhausen e Stoccarda.[2]
I tifosi dell'Arka sono legati a quelli del Cracovia Kraków e del Lech Poznań, con cui formano "la grande Triade" (Wielka Triada). Si è creata anche un'amicizia con i tifosi di Lechia Gdańsk, Śląsk Wrocław e Wisła Kraków, soprannominati "I tre Re delle grandi città" (Trzej Królowie Wielkich Miast). C'è una grande rivalità tra le due "alleanze".
La maggiore rivalità riguarda il Lechia Gdańsk. I tifosi di entrambe le squadre sono ostili tra di loro sin dal 1970 e le partite tra le due compagini sono state occasione per episodi di violenza.
