Dánia nem tudta kiharcolni a részvételt a 2016-os franciaországi Európa-bajnokságon, elbukta a Svédország elleni pótselejtezőt. elbukta a Svédország elleni pótselejtezőt.
„Közöltem a szövetséggel és a játékosokkal is, hogy befejezem – mondta Olsen a találkozó után. – Nincs értelme folytatnom, új edzőnek kell átvennie a helyemet. Rendkívül csalódott vagyok, amiért a játékosaim nem élhetik át, hogy ott lehetnek az Európa-bajnokságon.”
A játékosként 102-szeres válogatott Olsen 2000 óta irányította a dán nemzeti együttest – ezzel az egyik leghosszabb ideje foglalkoztatott szövetségi kapitány volt a világon –, s ezalatt két világ- és két
Európa-bajnokságra vezette ki csapatát.
Olsen az egyetlen a futballtörténelemben, aki futballistaként és kapitányként is legalább 100 válogatott meccsen vett részt.