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

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.

In 1982 Patrick Henry and many of her sister ships had their ballistic missile tubes disabled and were reclassified as attack submarines (SSNs).