Captain Andrew J. Hill relieved Captain William S. Post as CO on 10 January 1958. From 13 January to 23 January, NEWPORT NEWS participated in INTEX 1-58. 53 reservists were embarked for this cruise. On 15 February the NEWPORT NEWS departed Norfolk again, this time for two weeks in the Caribbean on "Operation Springboard". As a result of the competitive gunnery exercises fired, NEWPORT NEWS won 18 E's including the GOLD 'E', and received from COMCRUDIVTWO a message which read in part: "Congratulations to the professional gunners of the NEWPORT NEWS. Well Done."
RADM W.K. Romoser, Commander Amphibious Training Command US Atlantic Fleet, came aboard the NEWPORT NEWS on 14 March, to act as chief umpire for LANTPHIBEX 58. Upon completion of the exercise, lasting two weeks, the ship received the following message from VADM B.H. Hanlon, Commander Task Force 24: "I have been pleased with your excellent gunfire support. Well done." On 9 May the NEWPORT NEWS played host to 300 guests of the American Ordnance Association, who came aboard in Mayport, Florida and witnessed a demonstration of the latest equipment.
On 17 May, the ship visited New York City for Armed Forces Day.
Boarding 132 midshipmen, the NEWPORT NEWS began her third Midshipman Training cruise from Norfolk on 9 June 1958. During this cruise the ship visited the ports of Lisbon, Portugal, Copenhagen, Denmark and Hamburg, Germany. For this Midshipman cruise the ship was employed with Second Fleet under the command of Vice Admiral B.L. Austin. The heavy cruiser returned to NOB 8 August to disembark the midshipmen, where she remained until 2 September.
On the 2nd carrying RADM Lewis S. Parks, Commander Cruiser Force US Atlantic Fleet, she set sail for a tour of duty with the Sixth Fleet in the Mediterranean. This cruise included patrolling the coast of Lebanon, participating in Sixth Fleet exercises and visits to Rhodes and Athens, Greece, Naples and Genoa, Italy, Golfe Juan and Villefranche, France, Plama, Cartagena, Valencia, and Malaga, Spain, and Gibraltar. During the course of this cruise, the NEWPORT NEWS learned that she had been awarded the much coveted Operations Green "E". After three and one half months, the NEWPORT NEWS returned to its home port of Norfolk on 20 December. She underwent a period of upkeep until 15JAN59.