The contract to build her was awarded to the Electric Boat Division of General Dynamics Corporation in Groton, Connecticut, on 31 October 1973 and her keel was laid down on 27 December 1979.

[1][2] Albuquerque spent the remainder of 1983 engaged in operations at sea completing a variety of tests, examinations, certifications, and inspections.

At the beginning of 1984, Albuquerque reentered Electric Boat Shipyard for post-shakedown availability, returning to sea on 15 April.

October and November brought extended operations at sea in the Atlantic Ocean, and, in December, she underwent additional repairs at Electric Boat.

Two months later, she returned and took up local duty until November when she cruised to Florida to serve as a school ship for prospective commanding officers.

Albuquerque was commended for being the fastest and most cost-effective Engineered Refueling Overhaul (ERO) in history during the shipyard period, 22.3 months in length.

Albuquerque conducted a six-month deployment as part of the USS Harry S. Truman Carrier Strike Group from 13 October 2004 to 12 April 2005.

In July 2005, a fire-control technician named Ariel Weinmann deserted from Albuquerque and remained at large until he was arrested in 2006.

[8] On 6 August 2009, Albuquerque completed her change of homeport from Groton, Connecticut, to Naval Base Point Loma in order to maintain 60 percent of the submarine force in the Pacific in line with the 2006 QDR.

The deployment covered more than 40,000 nautical miles and included port visits in Brisbane, Australia; Yokosuka, Japan; and Guam.