In 2005, Cheadle was nominated for the Academy Award for Best Actor for his portrayal of Paul Rusesabagina in the film Hotel Rwanda.
Pada 2005, Cheadle dinominasikan Penghargaan Aktor Terbaik Akademi atas perannya sebagai Paul Rusesabagina dalam film Hotel Rwanda.