Paul Koeltzow was born on August 23, 1931, in Millington, Michigan. He enlisted in the U.S. Air Force on April 13, 1951, and entered Officer Candidate School in March 1953, receiving his commission as a 2d Lt in the Air Force on September 11, 1953. Lt Koeltzow next completed pilot training and was awarded his pilot wings at Webb AFB, Texas, in December 1954, followed by F-86 Sabre Combat Crew Training in May 1955. Capt Koeltzow served as an F-86 and F-101 Voodoo pilot from 1955 to 1962, and then attended F-105 Thunderchief Combat Crew Training before serving as an F-105 pilot with the 333rd Tactical Fighter Squadron at Seymour Johnson AFB, North Carolina, from October 1962 to March 1964. His next assignment was as an F-105 pilot with the 335th Tactical Fighter Squadron at Seymour Johnson from March to October 1964, followed by service as an F-105 pilot with the 8th Tactical Fighter Squadron and on the staff of the 49th Tactical Fighter Wing at Spangdahlem AB, West Germany, from October 1964 to May 1966. Maj Koeltzow served as an Operations Inspector with Headquarters U.S. Air Forces in Europe at Lindsey AS, West Germany, from May 1966 to February 1967, and then served as an F-105 pilot with the 388th Tactical Fighter Wing at Korat Royal Thai AFB, Thailand, from February to September 1967, where he flew 106 combat missions. His next assignment was with the 561st Tactical Fighter Squadron and on the staff of the 23rd Tactical Fighter Wing at McConnell AFB, Kansas, from October 1967 to August 1971, followed by service on the staff of the 6003rd Support Squadron at Hickam AFB, Hawaii, from August 1971 to December 1973. Col Koeltzow served as the Deputy Chief of Staff for Operations with 13th Air Force at Clark AB in the Philippines from December 1973 to August 1974, and then served as Vice Commander of the 56th Special Operations Wing at Nakhon Phanom Royal Thai AFB, Thailand, from August 1974 until his retirement from the Air Force on September 1, 1975.

His Air Force Cross Citation reads:

Major Paul F. Koeltzow distinguished himself by extraordinary heroism in connection with military operations against an opposing armed force as an F-105 pilot in Southeast Asia on 12 August 1967. On that date, Major Koeltzow led his force of twenty aircraft against the most heavily defended target complex in North Vietnam. Hampered by marginal weather, mechanical failures, and heavy and accurate hostile fire, Major Koeltzow led his force to the target, and although his aircraft was damaged by flak at the start of his bomb run, he overcame tremendous obstacles and continued his attack, destroying the target. Despite extensive damage to his aircraft, he engaged a flight of hostile aircraft and thwarted their impending attack on a crippled F-105. Through his extraordinary heroism, superb airmanship, and aggressiveness, Major Koeltzow reflected the highest credit upon himself and the United States Air Force.