Lavede sin første tegneserie allerede i gymnasiet og blev kontaktet af Henning Kure, Interpresse, der savnede en typisk dansk tegneserie på kioskernes hylder. Sammen med et forfatterteam - Henning Kure, Hans Rancke-Madsen, Per Vadmand og farvelægger Søren Håkansson - udvikledes albumserien Valhalla, der debuterede i 1979. Valhalla blev det tredie mest populære tegneseriealbum i Danmark, kun overgået af 'Lucky Luke' og 'Asterix', og det første internationale tegneseriealbum produceret i Danmark.

Peter Madsen havde en drøm om at omsætte Valhalla til film,  og i efteråret 1982 begyndte forfatterteamet at arbejde med manuskriptet og storyboard til filmen. For at motivere filmens handlingen og skaffe dramatisk spænding, videreudvikledes tegneseriens bifigur Quark til filmen.

Peter Madsen har, ud over albumserien Valhalla, produceret en række andre albums. I 1989 tildeltes han den danske tegneseriepris Ping, for sit arbejde.