Sarebresole was born in New Orleans, Louisiana. His French ancestors spelled the family name "Sarrebresolles".
He published Roustabout Rag in 1897, one of the earliest published ragtime pieces. Other noted Sarebresole compositions include "Get Your Habits On" from 1898 (which inspired the more popular sequel, "I've Got my Habits On"), "Fire's Out" from 1902, and "Come Clean" in 1905.
Paul Sarebresole died in New Orleans at the age of 36 and was buried in St. Louis Cemetery Number 3.