Cole joined the department on December 15, 1901, but resigned in 1915 to farm. He returned to law enforcement two years later, as a Deputy in the Jefferson County Sheriff's Office. He re-joined the Birmingham Police in 1923. He was heavily involved in investigating the series of axe murders blamed on a "syndicate" of killers. He was made chief of detectives in 1928 and was credited with solving the 1926 Moore-Thornton double murder near Roebuck which resulted in the execution of Horace DeVaughan.
Cole became ill and retired on February 1, 1935 to his home at 7532 2nd Avenue South. He died in 1940. He was survived by his two sons: M. H., a police motor scout and Eugene, an employee of the county comptroller's office; and by his daughter, Mrs H. G. Caudle.
- "Paul C. Cole is Taken By Death" (June 10, 1940) Birmingham Post