Впервые в Москву Майкл Джексон приехал в сентябре 1993 года. Его концерт был организован фирмой «Десса» и обошёлся ей в $1 000 000. Организатор гастролей — Самвел Гаспаров. Концерт прошёл 15 сентября на открытой площадке — Большой спортивной арене (БСА) стадиона «Лужники» при проливном дожде. Вскоре после концерта фирма прекратила своё существование из-за финансовых проблем, а стадион был закрыт на ремонт. Во время концерта шёл проливной дождь, лужи которого убирал обслуживающий персонал прямо во время выступления Майкла Джексона. В своем номере московского отеля Джексон написал балладу об одиночестве — Stranger in Moscow, которая вошла в альбом 1995 года History и вышла в виде сингла. Во время визита 1993 года Джексон останавливался в отеле «Метрополь». Второе выступление Джексона в России прошло 17 сентября 1996 года на московском стадионе «Динамо». Во время визита Майкл Джексон встретился с тогдашним мэром Москвы Юрием Лужковым, начальником службы охраны президента РФ Коржаковым, композитором Игорем Крутым. Во время визита 1996 года Джексон останавливался в отеле «Балчуг Кемпински». Альбом Invincible Следующий студийный альбом Джексона был записан только через шесть лет, его выпуск не раз откладывался. Лейбл «Sony» неохотно соглашался вкладывать миллионы долларов в затянувшийся процесс записи и последующей раскрутки альбома, что в конечном счёте привело к ссоре певца с гигантом звуозаписи. «Invincible» (Непобедимый), выпущенный в октябре 2001 года, содержал 16 треков, включая сингл «You Rock My World», в клипе к которому снялись известные актёры Марлон Брандо и Крис Такер. Альбом был неоднозначно встречен критиками, а цифры его продаж были в два раза скромнее, чем у «HIStory». Песня Invincible посвящена 15-летнему афро-норвежскому мальчику по имени Бенджамин Хермансен, который был убит группой неонацистов в г. Осло (Норвегия, 26 января, 2001). Омер Бхатти, близкий друг Джексона, был хорошим другом Бенджамина Хермансена. Майкл Джексон пишет в послании: «Этот альбом посвящен Бенни Германсену. Мы должны помнить: о человеке судить можно не по цвету его кожи, а по его личным качествам. Бенджамин, мы тебя любим. Покойся с миром». В целях продвижения альбома было организованно специальное празднование 30-летия сольной карьеры Майкла Джексона в Madison Square Garden которое произошло в сентябре 2001. Джексон появился на сцене рядом с его братьями, впервые с 1984 года. В шоу также включавший выступления Бритни Спирс, Mýa, Usher, Уитни Хьюстон, Tamia, 'N Sync, Слэш, Аарона Картера. Альбом породил три сингла, «You Rock My World», «Cry» и «Butterflys», последняя из которых не имела музыкального видео. «Unbreakable» должна была быть выпущена в виде сингла, однако в связи с рядом вопросов финансирования, Sony отказались выпустить его. В ноябре 2003 года Джексон выпустил сборник хитов «Number Ones». Вошедшие в сборник 18 треков включали 16 ранее изданных хитов, живое исполнение песни «Ben» и новый сингл «One More Chance». К концу 2004 года, продажи «Number Ones» по всему миру превысили 6 миллионов копий.