Born in Copenhagen on 22 March 1855, Madsen was the son of painters Andreas Peter Madsen and Sophie Thorsøe Madsen. He completed his schooling at Sorø Academy before attending C.V. Nielsen's art school in 1871. From 1872–1876, he studied at the Royal Danish Academy.
Madsen was greatly influenced in the early 1870s by the radical new departure in Danish culture, led by Georg Brandes, whose lectures at Copenhagen University he followed, and Holger Drachmann, who published his strong views on Danish art and on disappointing conditions at the Art Academy. In 1871, Drachmann went to Skagen, a fishing village at the northernmost tip of Jutland, to paint outdoor scenes and the local fishermen. Almost simultaneously, Madsen also arrived in Skagen.
Karl Madsen: Sketch of Hornbæk with church (1885)
During his first year at the Art Academy, he met Michael Ancher, whom he persuaded to join him in Skagen in July 1874. There he gave Anna Brøndum, later Anna Ancher, lessons in painting. His art work in 1873–1874 and from 1879–1880 shows that he was one of the key figures among the Skagen Painters. His portraits had a vitality comparable to those of Michael and Anna Ancher and Christian Krohg, but he lacked the virtuosity and sense of colour enjoyed by Peder Severin Krøyer, Viggo Johansen and the Swedish and Norwegian painters. His most interesting works are perhaps those from his last year in Paris where he came under the influence of the Barbizon school and possibly Édouard Manet, although they still tend to be rather dark and dull compared to the brighter works of the Impressionists who were influenced by the young Naturalists.
The gap between Madsen and the trends of the times as well as his own economic problems were probably behind his decision to become a professional writer. On Drachmann's recommendation, he became an art critic with Dagavisen in 1881. As a frequent contributor to Politiken and other periodicals, he became one of Denmark's most influential art commentators and critics. He was a champion of Dutch art and wrote a pioneering book on the art of Japan. As a museum expert, Madsen became recognized as an authority on Dutch art and brought about a reassessment of Danish art in the first half of the 19th century, especially with his biography of Johan Lundbye in 1895. He was the director of Statens Museum for Kunst from 1911-1925 , and director of Skagens Museum from 1928-1938.