Był brany od roli Johna McClane'a w filmie "Szklana pułapka", angaż otrzymał Bruce Willis.

Był brany pod uwagę do roli Michaela Cheritto w filmie "Gorączka". Ostatecznie otrzymał ją Tom Sizemore.

Odrzucił rolę Vincenta Vegi w "Pulp Fiction" na rzecz filmu "Wyatt Earp". Zastąpił go John Travolta.

Proponowano mu rolę Setha Gecko w filmie "Od zmierzchu do świtu", jednak odrzucił propozycję. Ostatecznie angaż otrzymał George Clooney.

Z powodu pracy nad "Urodzonym sportowcem" odrzucił rolę Idealnego Tommy'ego w filmie "Przygody Buckaroo Banzai. Przez ósmy wymiar". Angaż otrzymał Lewis Smith.

Ma dwie siostry: starszą Cheryl i młodszą Virginię.

Miał ponownie zagrać Boba w "Sin City 2: Damulka warta grzechu". Zastąpił go Jeremy Piven.

Zmarł w Malibu (Kalifornia, USA) w wyniku nagłego zatrzymania krążenia wywołanego kardiomiopatią, chorobą niedokrwienną serca i chronicznym alkoholizmem. Dodatkową okolicznością, która przyczyniła się do śmierci, była choroba zakrzepowo-zatorowa, czyli stan, w którym w naczyniach krwionośnych tworzą się skrzepy krwi, które następnie przemieszczają się i blokują inne naczynia, powodując zatorowość.

Z nieformalnego związku z Daną Mechling ma córkę Jessicę (ur. 24.03.1979).

Jest synem Elaine Madsen i Cala Madsena.

Jest autorem następujących tomików poezji:
- 1995 r. - "Beer, Blood and Ashes" i "Eat the Worm";
- 1998 r. - "Burning in Paradise";
- 2002 r. - "A Blessing of the Hounds";
- 2004 r. - "46 Down; A Book of Dreams and Other Ramblings";
- 2005 r. - "When Pets Kill";
- 2009 r. - "American Badass";
- 2013 r. - "Expecting Rain".

Miał początkowo wystąpić w roli Mickeya w filmie "Urodzeni mordercy", jednak studio Warner Bros chciało na jego miejsce kogoś o mniej przerażającej i łagodniejszej osobowości, aby złagodzić brutalność charakteru postaci. Zastąpił go Woody Harrelson.

Brano go pod uwagę do roli Matta Gavina w filmie "Jade". Angaż otrzymał Chazz Palminteri.

Był kandydatem do roli Vincenzo Coccotti'ego w filmie "Prawdziwy romans". Angaż otrzymał Christopher Walken.

Prowadził rozmowy w sprawie zagrania roli Johna McClane'a w filmie "Szklana pułapka". Rolę ostatecznie otrzymał Bruce Willis.

Początkowo miał grać Seana Harrisona w serialu "Hawaii", ale zastąpił go Michael Biehn.

W 2008 roku wystąpił w kampanii reklamowej Orange pt. "Don’t let a mobile phone ruin your movie".

Był jednym z najpoważniejszych kandydatów do roli sierżanta Mike'a Horvatha w filmie "Szeregowiec Ryan" Stevena Spielberga. Ostatecznie rola przypadła jego dobremu znajomemu, Tomowi Sizemore.

Wystąpił w następujących teledyskach:
- 2001 r. - "You Rock My World" - Michael Jackson;
- 2005 r. - "Kill The Music" - Every Time I Die;
- 2010 r. - "Obsession" - Sky Ferreira;
- 2012 r. - "As Long As You Love Me" - Justin Bieber;
- 2014 r. - "Black Widow" - Iggy Azalea feat. Rita Ora.

Ojcem chrzestnym jego dwóch synów: Hudsona i Calvina jest Quentin Tarantino.

Był kandydatem do roli Ivana Dargo w filmie "Rocky 4". Angaż otrzymał Dolph Lundgren.

Początkowo w filmie "Wściekłe psy" brano go pod uwagę do roli Pana Różowego. Ostatecznie postać tę zagrał Steve Buscemi.

Był kandydatem do roli Cyrusa "Wirusa" Grissoma w filmie "Con Air - lot skazańców". Angaż otrzymał John Malkovich.

Był kandydatem do roli detektywa Mike'a Logana w serialu "Prawo i porządek". Angaż ostatecznie otrzymał Chris Noth.

Rozważano udział Madsena w filmie "Bękarty wojny", gdzie zagrałby Babe'a Buchinsky'ego. Aktor jednak nie pojawił się na ekranie.

Początkowo to on miał zagrać Marva w filmie "Sin City - Miasto grzechu", jednak ostatecznie zagrał Boba, zaś w postać Marva wcielił się Mickey Rourke.

W filmie "Thelma i Louise" początkowo był kandydatem do roli Harlana Pucketta. Ostatecznie postać zagrał Timothy Carhart.

Z myślą o nim napisana była rola oficera Wendell 'Bud' White'a w "Tajemnicach Los Angeles", ale otrzymał ją Russell Crowe.

Był brany pod uwagę do roli Vince'a Korsaka w serialu "Partnerki". Angaż otrzymał Bruce McGill.

Odrzucił rolę Danny'ego McKnighta w filmie "Helikopter w ogniu", ponieważ zdjęcia kolidowały z pracą przy serialu "Zbrodnie Nowego Jorku". Angaż otrzymał Tom Sizemore.

Grany przez niego Blondyn z filmu "Wściekłe psy" zajął drugie miejsce w rankingu najczarniejszych charakterów w historii kina, amerykańskiego magazynu Maxim.