A kommunizmus évtizedeiben Kelet-Európát kétszer érintette a zenekar. 1967. április 13-án, még Brian Jones-szal valami véletlen folytán Varsóban lépett fel, a Sala Kongresowa rögzített széksoros, kissé protokoll-hangulatú termében. Keith Richard saját emlékei szerint leállította a zenekart és felszólította az első sorokban helyet foglaló párt- és állami szülők finnyáskodó gyermekeit, hagyják el a termet, és engedjék előre a hátul állókat. Akár így volt, akár nem, a vasfüggöny mögött nem sok kell a romantikus ellenállást dédelgető rockereknek, hogy kialakítsák a maguk legendáriumát az igazságpárti zenekarról.
1976-ban, Jugoszlávia fénykorában Zágrábig kellett elzarándokolniuk a keleti blokk Stones-rajongóinak; júniusban két koncertet adott ott a zenekar - Földes László élményszerűen rögzítette az eseményt Stones-könyvében. 1990 augusztusában következett Prága először, s azzal, hogy Jagger és Keith Richards találkozott és összebarátkozott Vaclav Havel akkori köztársasági elnökkel, az egész esemény valamiképp az új kelet-európai demokráciák nyugati elismerésének egyik aktusává vált. Ha eljön a Rolling Stones, akkor tényleg megtörtént a rendszerváltás - hihette egy pillanatra mindenki.
Az Urban Jungle turnén 1995. augusztus 5-én ismét Prágában lépett fel a Stones, felrúgva ezzel a "szokásrendet", amely szerint az üzletileg kevésbé frekventált területekről minden turnén más-más várost érintenek. (Bécsben Jagger rendszeresen köszöntötte a színpadról a régióbéli szlovák és magyar barátaikat is.) Három nappal később Budapest következett, ahol Jagger jól érezte magát, az emlékezetes, esős koncert után lement egy sörre a Bahnhof nevű szórakozóhelyre (állítólag éppen Mester Tamás karaokezott), Charlie Watts pedig kissé indignálódva nyilatkozott a városi közutak minőségéről.
1998-ban igazi felfedezőútra ment a Stones az ex-kommunista tömbbe: játszottak Tallinban, Chorzowban és Moszkvában is, megint felléptek Zágrábban és persze Prága sem maradt ki. A keleti koncerteknek pedig kialakult az a különös hagyománya, hogy az éppen aktuális politikai berendezkedés igyekezett saját legitimációját a Stones érkezéséhez kötni. Mikor híre ment, hogy új körútra készülnek az évezred elején, Belgrád és Peking is be akart kerülni a turnétervbe. A kínai vezetés egyébként az előző turné idején még azt közölte: nem kér a Stonesból, mert nem kívánt közlekedési káoszt okozhatna a fővárosban. Ám az idén nyárra lekötött "történelmi" koncertjeit lemondta a zenekar. Az őket személyesen meghívó Zoran Gyingyics meggyilkolása után nem akartak Belgrádban játszani, Peking pedig az SARS-fenyegetés miatt került ki a menetrendből.
Jagger augusztus 26-án, Prágában ünnepli 60. születésnapját, s a hírek szerint a régi barát, Václav Havel meglepetéssel készül. Valószínűleg Magyarországról is elzarándokolnak a hívek a Letna Parki-i koncertre, hiszen nem valószínű, hogy a Rolling Stones még egyszer Budapestre jönne játszani. Sőt, talán az sem, hogy mostani körútja végeztével újabb turnéra indulna. De hát már 1983-ban is erről szóltak a találgatások.