À la suite des mises sur cale des Clemenceau (22 novembre 1961 - 1er octobre 1997) et Foch (15 juillet 1963 - 15 novembre 2000), l’état-major de la Marine souhaitait la mise sur cale d'une troisième unité, dérivée des Clemenceau (2), dans le cadre de la tranche navale de 1958. Baptisé officieusement Verdun dans les coursives, son déplacement aurait atteint 35 000 tW : contre seulement 22 000 tW pour les Clemenceau (2). S’inspirant, manifestement, assez largement du concept de « porte-avions stratégique » identifié dans le Statut naval de 1955, révisé en 1956, et même du CVA-58 USS United States (1948 - 1949) , ce PA 58 Verdun devait être capable de mettre en œuvre un bombardier stratégique, et pour ce rôle était en concurrence les Générale aéronautique Marcel Dassault Mirage IVM ou bien le SNCASO SO-4060 Super Vautour, devant être capable d'emporter une bombe atomique grâce, notamment, à l’intégration au pont d’envol d’une catapulte axiale de 100 mètres, aux côtés d’une autre de 50 mètres.
En parallèle, une nouvelle proposition était avancée, dans le cadre du PA 59, pour substituer aux bombardiers stratégiques, un engin. Le missile de croisière Chance Vought SSM-N-8A Regulus (1955 -1964) de 500 nautiques de portée était employé aux États-Unis d’Amérique comme l’une des armes stratégiques. Cet armement fut déployé sur 4 croiseurs, 10 porte-avions (occasionnellement, en réalité) et 5 sous-marins. Afin de crédibiliser la force nucléaire américaine, le Chance Vought SSM-N-9 Regulus II était mis à l’étude dans l’optique d’en doubler la portée :1000 nautiques. La production débutait dès l'année 1958. Le missile entrait en service en septembre 1958 mais il était abandonné la même année, le 18 décembre 1958, au profit de l’UGM-27 Polaris A1 (Lockheed Corporation) : le premier Submarine Launched Ballistic Missile (SLBM), dénommé en France Mers-Sol Balistique Stratégique (MSBS).