Paul earned his bachelor and master of science degrees in aerospace engineering, from Texas A&M University. While working on the first degree, he was on an Air Force scholarship and was in the Corps of Cadets. After finishing his masters degree, he went on active duty in the Air Force working in military satellite operations.

Four years later, he came to Houston to work at the Johnson Space Center as one of the first engineers developing space station assembly operations. That work progressed into broader responsibility in preparing for all aspects of space shuttle missions to the space station, and then led to his selection as a flight director.