Un piccolo mistero contrassegna le origini dell’Olbia e la sua nascita. Le cronache del tempo non sciolgono il nodo e allora l’interrogativo continua a rimanere lì, appeso al cavallo di due anni. La più antica associazione cittadina è nata nel 1905 o nel 1906? È la memoria collettiva a tramandare e avvalorare la prima ipotesi, quella giornalistica a chiedere quantomeno di dubitarne. La prima testimonianza scritta data, infatti, 12 gennaio 1906: dalle colonne de La Nuova Sardegna si annuncia che “anche nel nostro paese, s’è formata una società ginnastica che ha preso il nome di OLBIA […] Ed i giovani sono accorsi numerosi ad iscriversi alla nuova società, e già l’Olbia conta circa cento soci”. Una spia, quello della grande immediata partecipazione, che rivela come l’idea, sviluppata e concretizzata dall’atleta Egidio Serra, covava verosimilmente da tempo e metteva dunque radici nelle settimane che portavano a conclusione il 1905.

Saggi di ginnastica, sfide podistiche e pariglie contrassegnano gli albori dell’attività dell’Olbia sino a quando, nel 1912, i quotidiani per la prima volta documentano, alla mattina del 19 giugno, di una “magnifica partita di Foot-Ball” disputata in città. Per le prime vere schermaglie calcistiche con le altre società del territorio bisogna, tuttavia, attendere la cessazione del periodo bellico quando, con varie denominazioni quali U.S. Olbia e L.C. Terranovese, la squadra cittadina inizia a darsi un organizzazione e a disputare incontri più o meno regolari contro squadre come Ilva e Audax Calangianus. Il 4 novembre 1924, si  gioca a Sassari il primo derby contro la Torres e l’Olbia, di granata vestita, perde 2-0. Il 19 aprile 1925, invece, al campo “Fausto Noce”, è la squadra gallurese a prevalere in un match conclusosi sul punteggio di 2-1 e con un rinfresco a base di vermouth, dolci e serata al cinema in onore degli ospiti. Cinque giorni prima e due giorni dopo, l’Olbia batte ancora per due volte i cugini sassaresi nel Torneo Sardegna, non disputando però la finale di ritorno contro il C.S. Cagliari (all’andata l’U.S. Terranovese perde 3-1 in casa) a causa dell’assenza di un giocatore e di un rinvio della gara non concesso.

I documenti ufficiali di fine anni Venti dicono che l’U.S. Terranovese, con divise rossonera e biancocrociata, è tra le società sarde affiliate alla Federazione. Ciò nonostante, tra il 1926 e il 1930, la squadra non prende parte al Campionato Sardo di 3^ Divisione e anche il terzo decennio del secolo si apre, salvo qualche sporadica partita disputata contro l’As Macomer, con una sostanziale inattività a livello federale. Il ritorno ufficiale sui campi è però dirompente: corre la stagione 1938/39 e l’Olbia si aggiudica, guidata dall’allenatore-giocatore Salvatore Satta detto “Menelik”, il campionato di Prima Divisione Regionale ottenendo così la prima storica promozione in Serie C. Con il nome di GIL Terranova, inserita nel girone B, domina la propria poule e arriva a giocare la finalissima contro il Monteponi Iglesias dopo aver eliminato l’Aquila Elmas e la forte Corsica Nuoro grazie a un gol del bomber Flavio Piras in un combattutissimo spareggio. A Cagliari, sul terreno di gioco di via Pola, è un autentico trionfo per i bianchi che annichiliscono l’avversario con un perentorio 6-0 marchiato dalla doppietta del funambolico Piro e ancora una volta da Piras, che va a segno ben 4 volte portando così a 14 il bottino di reti stagionali. Questa la formazione scesa in campo il 16 luglio 1939 per firmare l’impresa: Spano A., Jodice, Piccaredda G.M., Dejana, Satta, Pulina, Piro C., Picciaredda F., Piras, Crola, Careddu. Pochi mesi dopo, quasi in concomitanza con l’inizio del campionato di Serie C, la città riacquista, per decreto, il suo antico nome e così da Terranova ridiviene Olbia.

Sotto la presidenza di Gesuino Sardo e guidata da Mario De Palma in panchina, la prima volta dell’Olbia nella terza serie nazionale non inizia sotto i migliori auspici. Sconfitte piuttosto pesanti inaugurano la stagione 1939/40, ma la tenacia del gruppo dirigente e la ritrovata forma dei giocatori consentono presto di raddrizzare la barra del timone: il 15 ottobre 1939, a Olbia e in maglia bianca con lo scudetto dei quattro mori, il Terranova (che due settimane dopo acquisirà definitivamente il nome della città) vince la sua prima partita di Serie C per 1-0 contro lo Stabia, malgrado la multa minacciata dal tecnico avversario se i suoi giocatori non avessero segnato almeno tre reti ai galluresi. Un largo pubblico proveniente da tutto l’hinterland accorre a sostenere una squadra che va ad assumere un ruolo di rilevanza extracittadina e che ottiene un brillante dodicesimo posto alla sua prima esperienza di respiro nazionale. L’Olbia diventa così una bandiera del calcio sardo da sventolare con orgoglio anche in Penisola.

Nelle stagioni a seguire l’Olbia ritorna a disputare la 1^ Divisione Sarda, il massimo campionato regionale, sino a quando, nel 1943, il conflitto mondiale non impone alla Federazione la sospensione di tutti i campionati. Olbia, come del resto la gran parte dei centri dell’Isola e della Penisola, esce dalla Guerra in ginocchio ma vogliosa di rialzarsi al più presto. Anche per questa ragione, nell’estate del 1947, la dirigenza bianca si batte per ottenere la riammissione a quel campionato di Serie C abbandonato sette anni prima. A un rendimento da prima della classe in casa fa da contrappunto un pessimo rendimento in trasferta: un’Olbia combattiva e sorprendente si classifica dunque all’ottavo posto in un girone di ferro vinto dal Piombino. Il buon campionato non basta tuttavia a confermare la Serie C e il club scivola di nuovo nei campionati regionali.

Quella del 1948/49 è un’annata di passione che culmina con la retrocessione dalla Prima Divisione. È il preludio a un’interruzione dell’attività che estrometterà la squadra dai campionati per due stagioni. Il calcio tuttavia non chiude bottega e continua ad animare i campi e le strade cittadine con campionati locali che favoriscono il grande slancio della rinascita. Tra i tanti giovani appassionati si forgia in quegli anni “Sa Cavonera”, un gruppo di giovani olbiesi destinato a riportare entusiasmo a Olbia e l’Olbia a disputare di nuovo il massimo campionato regionale. Fanno parte di questa nuova generazione di talenti, tra gli altri, Gustavo Giagnoni, Marino Spano, Tonino Varrucciu e Bruno Garrucciu.

Si riparte nella stagione 1951/52 dalla Prima Divisione Sarda, diventata nel frattempo il quinto gradino dei campionati italiani. L’Olbia, guidata dal trio Paoli-Spano-Giagnoni, consegue un ottimo quarto posto che costituisce la solida base per la vittoria del campionato della ridenominata Promozione l’anno successivo. Guidati in panchina dal campione del mondo del 1938 Gino Colaussi, i bianchi inanellano vittorie sonanti e prestigiose contro avversari quali Tempio, Nuorese e Cus Cagliari. L’Olbia torna quindi a vincere, a divertire e a entusiasmare la sua gente ottenendo una meritata promozione nella Quarta Serie Nazionale.

Le traversate oltremare si circoscrivono però alla sola stagione targata 1953/54 che l'Olbia, pur lottando con vigore e coraggio, conclude all’ultimo posto. Tuttavia il calcio olbiese ha ormai messo radici e la fioritura di talenti si perpetua lungo tutto il decennio. Nelle stagioni a seguire la formazione bianca lotta ai vertici del calcio regionale sino a vincere di nuovo il campionato di Promozione nella stagione 1956/57. Si torna così a varcare il Tirreno e stavolta non con il ruolo di comparsa. Inserita nel girone F del Centro Italia e opposta a formazioni blasonate quali Torres, Grosseto, Ternana e Perugia, l’Olbia guidata in panchina dal maestro magiaro Lajos Kovacs e in campo dall’inseparabile duo Conte-Balzano, raggiunge un brillante sesto posto in classifica chiudendo il campionato imbattuta tra le mura amiche.

La rampante formazione bianca accresce anno dopo anno il volume di applausi e di meriti sulla platea italiana, divenendo, con il passaggio del decennio e sotto la presidenza di Elio Pintus, una presenza costante e virtuosa della Serie D, ma anche una certezza per tutto il movimento calcistico isolano. Sino ad ottenere la vittoria del campionato nella stagione 1967/68 grazie alla sagace guida di Palleddu Degortes, al carisma e alla classe dei vari Misani, Selleri e Bettella e alla penalizzazione per illecito sportivo inflitta al Latina. I cancelli della Serie C si riaprono così una terza volta per annunciare al calcio italiano il meritato ingresso della dama bianca nel professionismo.