Nella seconda metà degli anni '50 lo Stato Maggiore emanò le direttive per la realizzazione del secondo programma navale del dopoguerra, noto come Programma 1958, in cui venivano tracciate le future linee di sviluppo della Marina Militare. Non potendo contare su un potenziamento quantitativo, neanche a medio termine e sempre per motivi di bilancio, si decise di seguire la strada dell'evoluzione qualitativa, realizzando un numero limitato di piattaforme equipaggiate con impianti e apparati all'avanguardia e, in alcuni casi, innovativi rispetto allo standard navale europeo.

Il Programma 1958 prevedeva la realizzazione di:

• due incrociatori lanciamissili e portaelicotteri (classe Andrea Doria);
• due cacciatorpediniere lanciamissili (classe Impavido);
• quattro fregate portaelicotteri (classe Bergamini);
• quattro unità subacquee (classe Toti);
• la ricostruzione/trasformazione dell'incrociatore Giuseppe Garibaldi in lanciamissili, e quella del sommergibile Pietro Calvi.

Le unità avrebbero dovuto entrare in linea nei primissimi anni del decennio successivo; la scadenza venne rispettata per le fregate e, per il Garibaldi, mentre la realizzazione delle rimanenti unità si protrasse nel tempo per le difficoltà finanziarie derivate dall'inevitabile aumento dei costi iniziali, peraltro preventivati in un clima di stanziamenti già di per sè inadeguati.

L'esame delle categorie di naviglio previsto dal programma evidenzia chiaramente gli indirizzi dello Stato Maggiore, orientato verso l'affermazione del binomio missile-elicottero integrato in una piattaforma a primaria vocazione antiaerea ed antisommergibile. La scelta del primo elemento era in linea con le interpretazioni della guerra AA date dalle moderne marine occidentali: lo sviluppo dell'aeronautica, con l'introduzione dei velivoli a reazione, aveva infatti reso obsoleti i tradizionali impianti d'artiglieria, portando contemporaneamente alla ribalta un'arma - il missile -in grado di risolvere il problema della difesa delle unità navali contro i velivoli attaccanti. Il parallelo sviluppo dell'elettronica consentì di associare ai sistemi missilistici AA impianti di scoperta e di guida delle armi che semplificavano le operazioni di fuoco, migliorando le prestazioni generali dei sistemi stessi.

La scelta del secondo elemento del binomio, l'elicottero, derivò essenzialmente dalla circostanza che la MM non poteva disporre di velivoli ad ala fissa; a tal proposito, già nel 1954 era iniziata la costituzione dei primi reparti elicotteristici basati a terra, con materiale dapprima proveniente dagli USA ed in seguito realizzato in Italia su licenza. L'esito positivo delle prove di appontaggio condotte nell'estate del 1953 da un elicottero AB.47G su una piattaforma eretta a bordo del Garibaldi indusse la Marina ad imboccare la strada delle unità navali polivalenti dotate di componente elicotteristica antisom e delle relative attrezzature (ponte di volo, aviorimessa, ecc.), iniziando lo sviluppo di una nuova categoria di naviglio di cui l'Italia fu senza dubbio la precorritrice.

La necessità di piattaforme in grado di condurre autonomamente operazioni AS derivava anche dalla percezione della mi naccia sempre più concreta rappresentata dalla flotta subacquea dell'Unione Sovietica, la cui politica d'espansione verso gli oceani doveva giocoforza avvenire mediante un tipo di piattaforma capace di superare indisturbata i vincoli geografici cui era soggetta la sua marina (alcuni battelli sovietici avevano iniziato proprio in quegli anni a fare la loro comparsa in Mediterraneo, operando dalla base albanese di Valona).

Bisognava quindi potenziare la componente subacquea nazionale, e ciò avvenne con la costruzione delle quattro unità classe Toti, primi battelli italiani progettati secondo criteri che esaltavano al massimo grado le doti di silenziosità e manovrabilità in immersione. La validità dei Toti è stata confermata da un'intensa attività operativa iniziata a metà degli anni '60, e che vede le ultime due unità della classe ancora in servizio.

I progetti definitivi delle piattaforme elicotteristiche sfociarono nelle fregate AS classe Bergamìni, prime unità del genere al mondo, le cui peculiarità consistevano in un ponte di volo e in un hangar telescopico idonei a consentire l'impiego di un aeromobile tipo AB.47. L'unità capoclasse (Luigi Rizzo) iniziò nel 1961 l'attività sperimentale che, oltre a confermare la validità del progetto, servì da punto di partenza per successivi interventi migliorativi. A partire dal 1969 venne infatti ampliata la superficie del ponte di volo mediante l'eliminazione del pezzo poppiero da 76/62 mm, al fine di consentire l'operatività delle nuove macchine tipo AB.204 AS che, assieme al sonar a media frequenza e alla dotazione antisom (due impianti lanciasiluri trinati da 324 mm e un lanciabas), costituivano all'epoca un potenziale di tutto rispetto.

Nel 1957 iniziarono presso l'Arsenale di La Spezia i lavori di trasformazione del Garibaldi, operazione articolata sulla totale ricostruzione delle sovrastrutture e su una modifica parziale dello scafo. Il progetto mirava ad ottenere una piattaforma in grado di costituire un valido elemento nello schermo protettivo antiaereo di una task force (grazie alla presenza dei missili AA), integrando nel contempo mediante i missili balistici le capacità di proiezione di potenza insite in un complesso navale di questo tipo: un concetto sviluppato per inserire la Marina Militare nel novero delle "blue water navies", oltre che per ribadire l'importanza dell'Italia nel contesto NATO e la rilevanza strategica del Mediterraneo, fin troppo sottovalutata in sede di pianificazione politico-militare nazionale.

La trasformazione del Garibaldi comportò l'adozione di una poppa a specchio e la costruzione di un castello lungo circa 100 metri, su cui vennero installate due torri binate da 135/45 mm, il torrione sormontato dall'albero a traliccio, il grosso fumaiolo e otto pezzi da 76/62 mm; l'ampia tuga poppiera ospitò invece la rampa binata per i missili AA tipo Terrier con le relative apparecchiature di guida e i quattro pozzi di lancio per missili balistici Polaris, frutto di un progetto tanto rivoluzionario quanto funzionale, che fu molto apprezzato soprattutto dall'US Navy.

Proprio negli Stati uniti andava nel frattempo maturando l'idea di costituire una forza navale NATO (detta MLF, Multi Lateral Force) composta da 25 unità mercantili da 18.000 tonnellate e 21 nodi, convertite per trasportare un totale di 200 missili Polaris A3 e dotate di un'autonomia operativa di 100 giorni. Anche se il progetto fu presto abbandonato, è interessante notare come proprio il contributo italiano (palesato dal binomio Polaris/Garibaldi) avrebbe potuto rappresentare la soluzione tecnica del problema.

Nonostante l'esito favorevole dei lanci di prova effettuati nel 1961/62 sia in Italia che negli USA con l'impiego di missili balistici inerti, medesima sorte ebbe il programma di approvvigionamento degli ordigni destinati al Garibaldi; motivazioni d'ordine politico impedirono infatti l'acquisizione delle armi, e la Marina si ritrovò con una nave su cui una validissima e rivoluzionaria soluzione costruttiva potè essere sfruttata solo come deposito per materiali vari.

Le problematiche dell'integrazione militare occidentale in ambito sovrannazionale erano venute alla ribalta già a metà degli anni '50, in seguito alla stipula del trattato costitutivo della Comunità Europea di Difesa (CED). Alla componente navale di questo organismo era devoluto il compito della "protezione marittima ravvicinata", consistente nella difesa costiera di buona parte della massa continentale europea e nel sostegno alle operazioni terrestri. Il contributo di ciascuna nazione sarebbe stato commisurato alle rispettive potenzialità, e la Marina Militare prevedeva di trasferire in ambito CED cinque fregate, 11 corvette, 61 pattugliatori, 18 cannoniere/siluranti ed un complesso di ben 270 dragamine (in quest'ultima cifra erano incluse anche 180 unità ausiliarie, da requisire e attrezzare al momento).

Le competenze interforze assegnavano allo Stato Maggiore della Marina la responsabilità delle operazioni nei settori adriatico, ionico e tirrenico, ponendo alle sue dipendenze 23 squadriglie di unità navali nazionali ed estere di tutte le categorie. Nemmeno l'iniziativa della CED andò tuttavia a buon fine: l'Europa rimase così priva di una struttura militare che avrebbe potuto fornirle una maggiore credibilità generale, nella prospettiva della futura unione politica già a quel tempo in fase di sviluppo.