自身設立のレーベル"ISO"からの第1弾アルバム。プロデューサーには22年ぶりにトニー・ヴィスコンティを迎えて制作された。
アルバムタイトルは「異教徒」を意味しており、明日の見えない時代を生きることにテーマを重ねている。前年9月11日に発生したアメリカ同時多発テロ事件を彷彿とさせる世界観に仕上がっているが、歌詞自体は既にテロ以前に書いていたとのこと。
本作のレコーディングに取りかかる以前、ボウイとヴィスコンティは60年代の楽曲のセルフ・カヴァーに新曲を加えたアルバム『Toy』をレコーディングしており、それが本作の下地となっている。結局、同アルバムのリリースは見送られたが、制作の過程で生まれた新曲を軸にこの『Heathen』を完成させた。収録曲の「Slip Away」や「Afraid」は『Toy』のセッションで生まれた楽曲である。
同年に行われたツアーでは『Low』全曲と対比して演奏するという、セットリストが組まれたこともあった。
初回限定の2枚組が最初にリリースされ、次いで通常盤とLPサイズのジャケットが付属するCD、アナログと発売。そしてボウイのカタログで初めて5.1ch対応のスーパーオーディオCD（SACD）化されたのもこの『Heathen』である。最後に07年6月にリリースされた紙ジャケット仕様の再発版は、シングルのみ収録の曲などボーナス・トラックを多数収録している。
ゲスト・ミュージシャンにピート・タウンゼントやデイヴ・グロールらが参加している。
