Patrick Henry's keel was laid down by the Electric Boat Division of General Dynamics Corporation, in Groton, Connecticut, on 26 May 1958.

When she surfaced off Holy Loch, Scotland, on 8 March 1961, she had set a record for her type, cruising submerged 66 days and 22 hours.

For 18 months she received complete and extensive overhaul and repair operations, including refueling of the S5W reactor plant and modifications to permit the handling of the Polaris A-3 missiles.

After shakedown in mid-1966 off Puerto Rico and Cape Canaveral, Florida, Patrick Henry departed Charleston, South Carolina, in December for her eighteenth patrol, equipped with A-3 Polaris missiles and assigned to Submarine Squadron 14.

The purpose of the DASO was to ensure that the submarine's crew could safely meet the stringent requirements for handling, maintaining and operating her strategic weapons system.