Мейджор искал решение продолжавшегося кризиса в Северной Ирландии путем переговоров с ирландскими правительственными лидерами и с представителями Шин фейн, политического крыла Ирландской республиканской армии (ИРА), об одностороннем прекращении огня. В феврале 1995 Мейджор и ирландский премьер Дж. Брутон сообщили о новых шагах по политическому урегулированию в Северной Ирландии. Однако Мейджор настаивал на немедленном одностороннем разоружении ИРА. Вопрос о разоружении оставался главным препятствием к равноправному диалогу между ирландскими националистами и правительством Мейджора. В феврале 1996 ИРА отказалась от прежнего решения о прекращении огня; в портовом районе Лондона была взорвана бомба большой мощности, ответственность за эту акцию взяли ирландские националисты.

Несмотря на умеренный экономический рост в середине 1990-х годов, среди избирателей росло разочарование правительством Мейджора. К концу 1995 консервативное большинство в палате общин сократилось до 7 мест. Скандалы на почве секса и коррупции вместе с неумелыми действиями правительства по разрешению кризиса, связанного с "коровьим бешенством", еще больше навредили популярности консерваторов. В декабре 1996 Мейджор и консервативная партия утратили большинство в палате общин.

Мейджор назначил парламентские выборы на 1 мая 1997. Блэр немедленно начал кампанию под лозунгами обновления политики лейбористов, обещая продолжить экономическую политику правительства консерваторов, но одновременно провести децентрализацию (деволюцию) власти в Шотландии и Уэльсе, отменить право наследственных пэров голосовать в палате лордов, принять законы о минимальной заработной плате и о жестких мерах против несовершеннолетних правонарушителей. На выборах лейбористы одержали внушительную победу, получив 45% голосов и значительное большинство в79 мест в парламенте (418 против 165 мест, полученных консерваторами).