After a few months operating off the East Coast, Randolph deployed to the Mediterranean again on 1 July 1957.
Sau một vài tháng hoạt động ngoài khơi bờ Đông nước Mỹ, Randolph lại được bố trí đến Địa Trung Hải vào ngày 1 tháng 7 năm 1957.