The story
From the 1950s. First known use in a book of Captain Annis G Thompson, who was involved in the Korean War, The Greatest Airlift (1954). Originally used in the meaning "as soon as militarily possible" by military forces.
Etymology from Wiktionary, CC BY-SA 4.0.