Patrick Macdonald of The Seattle Times described "Stranger in Moscow" as "a pretty ballad interspersed with sounds of rain."
Patrick Macdonald của The Seattle Times mô tả "Stranger in Moscow" như "một bản ballad khá xen kẽ với các âm thanh của mưa".