Patrick Macdonald of The Seattle Times described "Stranger in Moscow" as "a pretty ballad interspersed with sounds of rain."
Ο Πάτρικ ΜακΝτόναλντ, της The Seattle Times, περιέγραψε το Stranger in Moscow ως «μια όμορφη μπαλάντα που διανθίζονται με τους ήχους της βροχής».