Sofus Madsen ble født i 1881 i Kristiania, som sønn av Sofie og (forfatteren og læreren) Theodor Madsen. Familien flyttet til Bergen da Sofus var tre år gammel, til Kalmargaten, ikke så langt fra Den Nationale Scene. Der vokste han opp, og der fikk han sitt kanskje første møte med skulpturen. I nabolaget hadde billedhuggeren Hans E. Johannessen sitt atelier. Sofus var ofte på besøk, og kanskje ble dette tidlige møte med kunsten medbestemmende for hans yrkesvalg.
Etter folkeskolen begynte Sofus Madsen på Bergens Tekniske Aftenskole der det ble undervist i frihåndstegning etter gipsavstøpninger og portrettegning etter levende modell. En av tegningene han laget etter en gipsavstøpning av en antikk skulptur, viser at han allerede i ung alder var en dyktig tegner og tidlig ble fortrolig med den klassiske kunstens idealer.
Madsen fortsatte sitt utdanningsløp som læregutt på Ingebrigt Viks rosettfabrikk og treskjærerverksted, som gipsmakerlærling. Vik, kunstneren bak blant annet skulpturen av Grieg i Byparken i Bergen, var på denne tiden, rundt 1900, travelt og innbringende opptatt med å forsyne en voksende by med takrosetter, stukkgesimser og fasadefigurer. Hos Vik lærte unge Madsen først og fremst et håndverk. Han så ikke tilbake på de tre årene hos Vik med særlig glede – det ble for lite kunst og for mye hardt arbeid.