Il Recreativo de Granada fu fondato il 6 aprile del 1931 da Julio López Fernández, che assunse la carica di presidente. La prima divisa scelta dal club fu interamente di colore bianco. La prima partita fu disputata contro il Deportivo Jaén, che fu sconfitto per 2-1. Il primo goal dell’incontro, e della storia del club andaluso, fu segnato da Antonio Bombillar. Iniziata la propria attività nelle serie regionali andaluse, nella stagione 1932-33 il club vinse il campionato di Tercera Regional per la Región Sur, venendo per la prima volta promosso in Tercera División e, già l’anno successivo, accedendo alla serie cadetta del calcio spagnolo. Dopo la lunga parentesi della Guerra Civile, che vide tre anni di interruzione delle competizioni calcistiche, il Recreativo fu inserito in Segunda División e, dopo due stagioni, raggiunse la massima categoria del calcio spagnolo grazie a un’impressionante risalita dalle serie inferiori, che portò il club dalla Tercera Regional alla Primera División nell’arco di soli sette campionati. Il Granada – che assunse in questo periodo la denominazione odierna e, dal 1939, i colori sociali attuali- confermò il proprio periodo positivo nella stagione 1940-41, culminata con la prima storica promozione in Primera: il campionato era formato da due gironi e le prime due classificate avrebbero disputato un piccolo campionato con partita di andata e di ritorno. Il Granada giunse secondo nel suo gruppo e incontrò il Deportivo La Coruña, il Castellón e la Real Sociedad, che dopo il conflitto bellico si chiamava Donostia. Con due vittorie ottenute fuori casa contro la Real (con gol granadino del basco Cholín) e il Castellón il Granada vinse il campionato con una giornata d’anticipo: l’incontro finale vide la vittoria del Deportivo, ma ciò non arrestò i festeggiamenti che animarono per una settimana la città. Il Granada raggiunse così la massima serie: era una squadra giovane, piena di qualità, con elementi che entreranno nella storia del club: Floro, Millán, González, Maside, Bonet, Sosa, Guijarro, Trompi, Cholin, Bachiller e Liz. Il presidente Ricardo Martín Campos visse momenti felici, ma l’allenatore Victoriano Santos abbandonò a sorpresa la compagine andalusa un mese prima di terminare la stagione, per morire poco tempo dopo vittima di tubercolosi. Dopo quattro stagioni disputate in Primera, con il raggiungimento dell’ottavo posto in classifica nel 1943-44, la stagione 1944-45 vide retrocedere il Granada. Il club dovette attendere dodici anni, con la stagione 1956-57, per rientrare nel giro delle grandi: all’epoca il presidente era Pepe Bailón[4]. La battaglia per la promozione fu coronata dal successo, ma il presidente e il segretario Bueso furono sanzionati per aver tentato di corrompere il club avversario. La squadra vinse la Segunda División, gli allenatori furono Álvaro Pérez a cui subentrò Pasarín, e questa la formazione base: Candi, Vicente, Suárez, Pérez Andreu, Galvis, Baena, Guerrero Vida, Igoa, Rius y Navarro. Il Granada rimase nella massima serie quattro stagioni, per poi retrocedere in seconda divisione, che disputò per cinque anni consecutivi. Nel 1965-66 la compagine ottenne la sua terza promozione nella massima serie, di nuovo con Pepe Bailón alla presidenza, e l’immarcescibile Jenő Kálmár in panchina. Per ottenerla fu necessario uno scontro fratricida contro il CD Málaga, visto che i granadini erano arrivati al secondo posto: ci fu una vittoria a Los Cármenes e un pareggio alla Rosaleda con rete decisiva del granadino Eloy Matute[4]. La formazione base era: Otero, Barrenechea, González, Tosco, Sande, Lorenzo, Santos, Rafa Almagro, Ureña, Gerardo y Vicente; sei titolari provenivano dalla cantera, cinque di questi erano nati a Granada (González, Almagro, Eloy, Ureña y Gerardo). Dopo solo una stagione nella massima serie il Granada viene tuttavia di nuovo retrocesso dopo gli spareggi contro il Betis di Siviglia: la sconfitta a Los Cármenes nell’incontro di andata provocò l’allontanamento dell’allenatore Ignacio Eizaguirre, sostituito da Manolo Ibáñez: questi non riuscì comunque a rovesciare le sorti, venendo sconfitto anche nella gara di ritorno. La retrocessione comportò le dimissioni di Bailón e l’accesso alla presidenza di Cándido Gómez. Per la stagione 1967-68 Candi mantenne quasi lo stesso organico effettuando solo sei acquisti, assunse come allenatore Joseíto e, con lo zamorano ex madridista in panchina, il Granada disputò una stagione eccezionale che la vide raggiungere il primo posto della Segund. La stagione 1968-69 vide l’inizio della fase migliore della storia del Granada in Primera División. Negli otto campionati infatti seguenti la compagine andalusa riuscì a mantenersi stabilmente nella massima serie, e per due volte (1972 e 1974) si classificò al sesto posto, al momento il miglior piazzamento della storia del club. È in questo periodo che il Granada viene soprannominato “ammazzagiganti”, grazie alle vittorie conseguite, tra gli altri, contro il Real Madrid, il Barcellona e l’Atletico di Bilbao. Nel 1975-76 Miguel Muñoz venne assunto come allenatore dopo aver allenato il Real Madrid per 15 anni e la nazionale spagnola per altri cinque, ma la sua permanenza fu breve: il Granada fu infatti subito retrocesso.