Babayaro began his playing career at Nigerian side Plateau United, before moving to Belgian club Anderlecht in 1994, and eventually would make a name for himself, quickly gaining first-choice status although still a teenager. Babayaro set records as the youngest player to make an appearance and to receive a red card in the UEFA Champions League. He was sent off in a match between Steaua Bucuresti and his club Anderlecht (1–1), aged 16 years and 86 days. Celestine is widely regarded as the best Nigerian full back ever to have lived alongside Taribo West.
Babayaro was signed by Chelsea after being spotted by scout Lewis Durkin in April 1997. He moved for a transfer fee of £2.25 million, a club record paid for a teenager at the time. He made his debut in the UEFA Cup Winners' Cup against Slovan Bratislava, but an injury sustained in the 6–1 win over rivals Tottenham Hotspur in December 1997 ruled him out for the rest of the season. This meant he missed their victories in the 1998 Football League Cup Final and the 1998 UEFA Cup Winners' Cup Final. However, with Chelsea he went on to win the 1998 UEFA Super Cup, the FA Cup and Charity Shield in 2000, and reached the 2002 FA Cup Final. He was also instrumental in Chelsea's memorable run in the 1999-2000 UEFA Champions League. However it was to end in heartbreak for Babayaro as he was sent off in extra time against Barcelona as they bowed out of the competition at the quarter final stage. He faced competition from Graeme Le Saux during his seven-year spell, but managed to play over 200 games for the London side. His acrobatic celebrations with backflips were noted and loved by the fans of the club.
In January 2005, he left Chelsea to join Newcastle United on an undisclosed fee, where he established himself as first choice left back. He scored his first and what turned out to be his only Newcastle goal in a 3–1 win over Coventry City in the FA Cup.
In September 2006, Babayaro was given a three-match ban by The Football Association for slapping Liverpool striker Dirk Kuyt in the face, while Liverpool took a corner The slap was not seen by the referee Mark Halsey, but later footage showed Babayaro punch the Dutchman in the face. Babayaro accepted the allegations and apologised to Kuyt.