I 1902 fikk Sofus Madsen Den norske stats stipendium for billedskjærere. Dette gjorde det mulig å dra til Kunstakademiet i København der han ble elev av Carl Aarsleff – og venn av Kai Nilsen, en kunstner man kan ane spor av i Madsens kunst.
I København hadde han også rik anledning til å studere skulptur av ypperste klasse, i byens museer og samlinger. Ikke minst skal fransk skulptur ha opptatt ham på den tiden. Under Københavnoppholdet formet han sitt første hovedverk i stort format, Gravfred. Dette brakte Madsen anerkjennelse og Det Hjelmstjerne-Rosenkronske Legat – og med ett hadde han fått midler å reise for. I 1905 finner vi Madsen i Berlin, som assistent for den tyske billedhugger av islandsk avstamning, Harry Magnussen. Magnusson tok livet av seg etter å falt i unåde i kunstnermiljøet, og Madsen formet ved den anledning sitt mørke, nærmest groteske Dødsmasken.
Madsen hadde tenkt seg videre til Italia, men dette ble det ikke noe av. I 1910 dro han imidlertid til Paris. Pengemangel hindret regelmessig undervisning, og den store inspirasjonskilden ble derfor den skulpturkunst han kunne se i museene. De billedhuggere som skal ha interessert ham mest, var antikkens mestre og videre Michelangelo, Rodin og Meunier.
I 1914 var Madsen igjen i København. Samme året hadde han sin første separatutstilling i byen, og i en avis kunne man lese at «mellom Kunstvenner i København har denne Udstilling vakt en for Sofus Madsen smigrende Opmærksomhed.»
