SSBN-601 wurde 1958 in Auftrag gegeben und nur drei Wochen später auf Kiel gelegt. Bauwerft war Newport News Shipbuilding. Ende 1959 lief das Boot vom Stapel und wurde von Mrs. Hanson E. Ely II getauft. Im September 1960 wurde das Boot offiziell in Dienst gestellt.
Nach Torpedotest folgte am 22. Dezember 1960 der erste Testschuss einer UGM-27A Polaris. 1961 nahm die Robert E. Lee an U-Jagd-Übungen gegen Tosk teil. Nach einer Werftliegezeit verlegte die Robert E. Lee in ihren neuen Heimathafen in Holy Loch, Schottland. 1965 wurde in San Francisco eine erste Überholung durchgeführt, in der das Raketenstartsystem modernisiert wurde. 1967 kehrte das U-Boot nach Holy Loch zurück.