Sullivan was born in Cranston, Rhode Island, and graduated from Brown University as salutatorian and Class Orator of the class of 1943. His senior address was on America's duty to "aid in repairing not only the damage suffered by our Allies, but also that sustained by our enemies." After graduation, he entered the Navy and served as a gunnery officer on a destroyer, the "USS Hambleton". The "Hambleton" escorted North Atlantic convoys, and served off North Africa and Italy before participating in the D-Day invasion of Normandy and the invasion of Okinawa. He had the senior watch on the Hambleton when it entered Yokohama harbor for the Japanese surrender.