В течение многих лет ей не разрешалось гастролировать за пределами Советского Союза. Этот запрет был снят в 1959 году Никитой Хрущевым.
Благодаря возможности путешествовать по миру в составе Большого театра, ее мастерство как танцовщицы получило широкое признание. Она установила высокий стандарт для балерин в технике и драматическом присутствии. Хрущев разрешил ей поехать на гастроли Большого театра в Нью-Йорк и был безмерно доволен, прочитав отзывы о ее выступлениях. Он обнял ее по возвращении.
В течение нескольких лет она была признана "международной суперзвездой" и постоянным "кассовым хитом во всем мире". Советский Союз относился к ней как к любимому культурному эмиссару, как к "танцовщице, которая не дезертировала". Хотя она много гастролировала в те годы, когда другие танцовщики, включая Рудольфа Нуреева, Наталью Макарову и Михаила Барышникова, дезертировали, Плисецкая всегда возвращалась в Россию.
Плисецкая объясняет, что для ее поколения, и в частности для ее семьи, дезертирство было вопросом морали. Однажды она спросила свою мать, почему их семья не уехала из Советского Союза, когда у них была такая возможность, в то время они жили в Норвегии. Мама ответила: "Миша никогда бы не стал предателем".