22 Kasım 1965'de Kopenhag, Danimarka'da hemşire bir anne ve taksi şoförü bir babanın oğlu olarak doğdu. Kendisi gibi aktör olan kardeşi Lars Mikkelsen ile Nørrebro'da büyüdü. Jimnastikçi olarak eğitim aldı. Daha sonra Göteborg'da bale okulunda dans eğitimi aldı. Yaklaşık on yıllık profesyonel dansçı iken oyunculuk alanında kariyer yapmak için, 1996'da Århus Tiyatro Okulu'na gitti. Danimarka'nın en seksi adamı olarak nitelendirilen başarılı aktör, 3 filmden oluşan ünlü yönetmen Nicolas Winding Refn'ın suç-gerilim film serisi Pusher‘ın ilk iki filminde Tony adında bir uyuşturucu satıcısını canlandırarak Danimarka’da ün kazandı. İkinci Pusher filminde gösterdiği performans ile En İyi Erkek Oyuncu Bodil Ödülü, En İyi Erkek Oyuncu Robert Ödülü ve En İyi Erkek Oyuncu Zulu Ödülü’nü kazandı. 1999 senesinde Mikkelsen, tarzının dışına çıkarak yine Refn’in Bleeder adlı filminde çekingen kişilik bozukluğu yaşayan bir film uzmanı olan Lenny karakterini canlandırdı. Peter Thorsboe’nin Danimarka televizyon serisi Rejseholdet‘te Allen Fischer karakterine, 2000-2004 yılları arasında 32 bölüm boyunca hayat verdi.Mikkelsen'i uluslararası platformda tanıtan ilk rolü 2004 yapımı Jerry Bruckheimer‘ın filmi King Arthur‘da canlandırdığı Tristan karakteri oldu. 2006 yılında gösterime giren bir James Bond filmi olan Casino Royale filminde uluslararası terör örgütlerine muhasebecilik yapan Le Chiffre rolünü canlandırdı. Bu filmlere kadar onlarca ödüle layık görülen aktör, 2012 yılında yer aldığı Danimarka yapımı Jagten (The Hunt) adlı filmde Lucas adlı sıradışı başrol karakteri canlandırdı. Bu performansı ile Cannes Film Festivali’nde en iyi aktör ödülünü kazandı. . Yine aynı yıl çok beğenilen ve Oscar adayı filmlerden olan tarihi drama türündeki A Royal Affairs‘de başrolde yer aldı. 2013 senesinde ise Bryan Fuller‘in yaratıcısı olduğu ünlü Hannibal adlı televizyon dizisinde, Dr. Hannibal Lecter karakterini canlandırmaya başladı. Bütün hayatı boyunca Kopenhag'da yaşayan Mikkelsen, 2012 yılında Hannibal'ın çekimleri için Toronto'ya gittiğinde oraya taşındı. 2016'da Marvel'ın Doktor Strange adlı filminde Benedict Cumberbatch, Rachel McAdams ve Tilda Swinton ile birlikte başrolde yer aldı. Rihanna'nın "Bitch Better Have My Money" klibinde oynadı. 2016'da 69. Cannes Film Festivali'nde jüri üyeliği yaptı. Star Wars film serisinin ilk antoloji ve ilk bağımsız filmi olan Rogue One: Bir Star Wars Hikayesi'nde Galen Erso karakterini canlandırdı. 1987 yılından beri sevgilisi olan koreografici Hanne Jacobsen ile 2000 yılında evlendi. Viola ve Carl adlarında iki çocukları vardır.