Paine enlisted in the Army in 1918, undergoing pilot training under the Air Corps and receiving a commission as a second lieutenant. After his discharge in 1919, Paine flew planes for various companies until joining the Air Mail Service in 1920.[5] He and fellow aviator Ray Crozier were granted a license in 1919 to operate the self-described first commercial international mail and passenger air service in North America, between California and Baja California.[6]
During his air mail career, Paine became nationally recognized for his accomplishments while flying through rugged terrain and snowstorms in the Rocky Mountains.[5] From 1920 to 1922, Paine flew primarily out of Cheyenne, Wyoming, and Salt Lake City, Utah, for the Air Mail Service, becoming one of the top fliers in the Western Division.[4][7] On April 30, 1922, Paine died of an accidental gunshot wound to the head sustained at his home in Salt Lake City.[4] Paine was buried at Evergreen Cemetery in Everett.[1]
In 1941, the Army Air Corps renamed the Snohomish County Airport in his honor.[8] A bust of Paine was installed at the base's clubhouse in 1955, but later disappeared.[5] A life-size statue of Paine was unveiled in 2019 at the airport's new passenger terminal.[9]