She was laid down on 19 August 1972 by the Newport News Shipbuilding & Dry Dock Company as a nuclear-powered, guided-missile frigate, DLGN-38; launched on 14 December 1974; sponsored by Virginia S. Warner, daughter of the Honorable John Warner, former Secretary of the Navy; reclassified as a nuclear-powered, guided-missile cruiser and redesignated CGN-38 on 30 June 1975; and commissioned on 11 September 1976, Capt. George W. Davis, Jr., in command.

During the first six months of her commissioned service, Virginia ranged the eastern seaboard of the United States and cruised in the West Indies several times conducting myriad of post-commissioning tests and shakedown training. On 25 April 1977, she entered the Norfolk Naval Shipyard for a five-month, post shakedown availability. She completed her final sea trials on 28 September and began duty as an operational unit of the Atlantic Fleet. In November, she cruised along the New England and Canadian coasts, participating in anti-submarine warfare exercises. In December, she returned to the West Indies for missile firings on the Atlantic Fleet weapons range. She completed that mission on 13 December and reentered Norfolk three days later to begin holiday leave and upkeep in her home port. The beginning of 1978 found her still in Norfolk; but, by mid-month, she returned to sea in the Virginia Capes operating area for a series of local operations. On 28 January, however, she departed Norfolk to return to the area along the Florida coast and in the West Indies for a series of special tests conducted under the auspices of the Office of the Chief of Naval Operations. The guided-missile cruiser returned to Norfolk on 23 March and resumed local operations.

That employment lasted until 23 August when Virginia embarked upon a cruise to northern Europe to participate in Exercise Northern Wedding, a NATO exercise, the purpose of which was to test the ability to reinforce NATO forces in western Europe. During that deployment, she visited Oslo in Norway, Rotterdam in the Netherlands, and Portsmouth in England. The warship departed the latter port on 3 October and reentered Norfolk on the 12th. On 16 November, she put to sea for training exercises in the Gulf of Mexico. During that voyage, she made a port visit at Mobile, Alabama, and conducted naval gunfire support training at Vieques Island near Puerto Rico. She made another port visit to the island of St. Thomas on 6 December and 7 December before heading home. Virginia reentered Norfolk on 11 December and began preparations for her first deployment to the Mediterranean which was scheduled to commence in early 1979.

As part of an Indian Ocean deployment in 1980, she crossed the Indian Ocean to the Republic of the Philippines, for emergency Sonar dome repairs. During her third Mediterranean deployment in 1983, she patrolled off Beirut and fired nearly 300 five inch rounds into Lebanon, many in defense of the strategic mountain town of Suk El Gharb. Virginia provided emergency assistance after the Beirut Marine barracks bombing. She was honored as Sixth Fleet Top Hand for that extended deployment. In 1984, she entered Norfolk Naval Shipyard for her single major overhaul and was converted to the Navy's first strike cruiser with the addition of the Phalanx CIWS, Tomahawk missile and the SM-2 extension of her surface to air capability. During this overhaul, the aft helicopter hangar and elevator were removed and the space refitted with 2 Armored Box Tomahawk cruise missile launchers (4 missiles each) on deck and an Engineering Department training space below.

In December 1990, Virginia deployed to the Mediterranean in support of Operations Desert Shield and Desert Storm. Most of the six-month deployment was spent in the Eastern Mediterranean Sea, off the coast of Israel, Lebanon, and Syria. There she commanded a strike group of 4 vessels including a destroyer and 2 SSNs. In January 1991, she fired two Tomahawk cruise missiles from the Mediterranean to Iraq, which was at the time the longest combat firing of a Tomahawk. She also directed the launching of four other Tomahawks from the two submarines in the task group.

She was decommissioned and stricken from the Naval Vessel Register on 29 November 1994, Virginia entered the Navy's Nuclear-Powered Surface Ship and Submarine Recycling Program on 31 March 1999.

Her missile launchers are now on display at the Norfolk Naval Shipyard, Portsmouth, Virginia.