Bruhns was born in Silesia, Germany. He studied at the Royal Conservatory of Dresden under Felix Draeseke and Hugo Riemann and later studied in Paris with Camille Saint-Saëns. Bruhns worked as a conductor of grand opera in cities throughout Europe. He also worked as an accompanist in concert and recital tours with singers throughout Europe and the United States. He composed the music to the theatrical work Ib and Little Christina—with a libretto by Basil Hood—which was first produced at the Prince of Wales Theatre on 15 May 1900.
In 1910, Bruhns immigrated to the United States, ultimately settling in Cranford, New Jersey. He produced a significant number of marches, patriotic American songs, and popular songs. His more notable works include American Rhapsody, the symphonic poem Valley Forge, the marches American Heroes and National March, and the song Lady Moon Song. He was one of the earliest members of the American Society of Composers, Authors and Publishers.