The contract to build Ulysses S. Grant was awarded to the Electric Boat Division of General Dynamics Corporation in Groton, Connecticut, on 20 July 1961 and her keel was laid down there on 18 August 1962.

She was deployed to Guam, in the Mariana Islands, and conducted 18 deterrent patrols operating from there equipped with Polaris ballistic missiles before returning to the United States in 1969.

After an overhaul and conversion to carry Poseidon ballistic missiles at Puget Sound Naval Shipyard at Bremerton, Washington, Ulysses S. Grant was deployed to Holy Loch in Scotland in 1970, and operated in the European area until September 1977.

Ellis, completed what was called "The best DASO (Demonstration and Shakedown Operation) in 10 years,"b which concluded with the firing of a test missile on 31 July 1980.

On 7 April 1987, two crewmen of Ulysses S. Grant were swept off the submarine's missile deck during heavy seas 3 miles off Portsmouth, New Hampshire.