Okres sławy W 1993 wydali album pt. Everything Changes, bazujący na oryginalnych materiałach Gary’ego Barlowa. Z krążka wypłynęły przeboje: „Pray”, „Relight My Fire” (z gościnnym udziałem Lulu), „Babe” oraz tytułowy utwór; wszystkie dotarły choć na tydzień do pierwszego miejsca na liście UK Singles Chart. Piąta piosenka z albumu – „Love Ain’t Here Anymore” dotarła do trzeciego miejsca w brytyjskim zestawieniu przebojów. Przez cały 1994 intensywnie koncertowali; tylko we wrześniu zagrali 22 koncerty na wypełnionych stadionach. W tym okresie zdobyli międzynarodową sławę w Europie i Japonii, gdzie zaczęli grać regularne koncerty; w 1994 odbyli swoją pierwszą, regularną trasę po krajach Europy. Prasa określała ich jako „Beatlesami lat 90.”, amerykański „Rolling Stone” opisał ich za to „najgorętszymi na świecie idolami nastolatek”.
W trakcie lat 1993–1995 osiągnęli ogromną sławę w Wielkiej Brytanii, czego dowodem są liczne okładki czołowych pism w Anglii tj. Smash Hits czy GQ. Byli jedną z najlepiej promowanych grup ich czasów, chętnie zapraszano ich na liczne koncerty, uroczystości i rozdania nagród, a ich wizerunek znajdował się na licznych gadżetach, m.in. plakatach, lalkach i poszewkach. Fanklub zespołu w tym okresie liczył ponad 150 tys.