He commanded Destroyer Flotilla Four, United States Atlantic Fleet in 1955–1956 and was Director of Naval Intelligence from 1956 until 1960.

Holding these posts during the beginning of the space race, Frost was involved in early decisions to promote surveillance satellites such as the navy's ELINT program.

In an effort to reduce tensions, soon after his arrival at NSA, Frost appointed Robert F. Rinehart as chairman of the National Security Agency Scientific Advisory Board specifically because he was the newest member of the board with only a few months' experience and so had fewer "pre-acquired biases" in Rinehart's words.

According to the NSA, "In 1962, when Vice Admiral Laurence Frost was unexpectedly transferred from his position" Gordon Blake was his replacement.

He is listed as a rear admiral by the John F. Kennedy Presidential Library, which holds an 11-page transcription of an oral interview he gave in 1970.