Ostatecznie Kasparow rozegrał mecz z Kramnikiem pod egidą nowej organizacji o nazwie Braingames.com. Mecz odbył się w 2000 w Londynie i przyniósł ogromną niespodziankę. Doskonale przygotowany Kramnik wygrał dwie partie nie przegrywając żadnej. Po raz pierwszy od szesnastu lat Kasparow został pozbawiony w meczu tytułu mistrza świata.
Pomimo utraty tytułu Kasparow pozostał postacią numer jeden w światowych szachach. Występował już nieco rzadziej w turniejach, jednak w dalszym ciągu był niezwykle trudny do pokonania. W 2001 zwyciężył w doskonałym stylu turniej w Wijk aan Zee. W 2004 na turnieju w Linares dał się jednak wyprzedzić Kramnikowi, dzieląc drugie miejsce z Péterem Lékó.
W tych latach podejmowano wiele działań na rzecz zjednoczenia światowych szachów i wyłonienia niekwestionowanego mistrza świata, jednak konflikty interesów najważniejszych postaci okazały się zbyt trudne do przezwyciężenia. W 2003 nie doszło do planowanego meczu unifikacyjnego pomiędzy Kasparowem a mistrzem świata FIDE Rusłanem Ponomariowem. Fiaskiem zakończyły się również próby zorganizowania meczu Kasparowa z następcą Ponomariowa, Rustamem Kasimdjanovem.