In 1865 Olsen went to Trondheim as apprentice to a craftsman. He also studied composition and the organ from Fredrick and Just Lindeman, and sometimes substituted for Just as the organist in the Trondheim cathedral. In 1870, having given up his apprenticeship, he moved to Leipzig where he studied under Oskar Paul at the music conservatory until 1874. There he wrote his Symphony in G major, and began his opera Stig Hvide.
In 1874 he became a teacher in Christiania (now Oslo), where he spent most of the rest of his life. He conducted the Christiania Artisans' Choral Society from 1876 - 1880, the Music Society orchestra from 1877 - 1880, and the freemason's orchestra from 1894 - 1908. From 1884 he was the music director of the Akershus 2nd Brigade. From 1899 - 1920 he was a music inspector.
He had married Marie Hals, the daughter of a piano manufacturer, in 1879. He died in Oslo in 1927.
Olsen's operas were influenced by Richard Wagner. Another strong influence was the traditional Joik form of song, as he was involved in collecting folk tunes while in the military. These influenced the large number of military marches he composed, and the nationalist tradition was also represented in his stage works.
His compositions include: