Stebbins studied music in Buffalo and Rochester, New York, then became a singing teacher. Around 1869, he moved to Chicago, Illinois, to join the Lyon and Healy Music Company. He also became the music director at the First Baptist Church in Chicago. It was in Chicago that he met the leaders in the Gospel music field, such as George Root, Philip Bliss, and Ira Sankey.

At age 28, Stebbins moved to Boston, Massachusetts, where he became music director at the Claredon Street Baptist Church; the pastor there was hymnist Adoniram Gordon. Two years later, Stebbins became music director at Tremont Temple in Boston. Shortly thereafter, he became involved in evangelism campaigns with Moody and others. Around 1900, Stebbins spent a year as an evangelist in India, Egypt, Italy, Palestine, France and England.