Celestini pochodzi z Lozanny i tam też rozpoczynał piłkarską karierę w klubie Lausanne Sports. W 1995 roku zadebiutował w barwach tego klubu w Nationallidze A, ale początkowo nie grał w pierwszej jedenastce. W wyjściowym składzie Celestini zaczął grywać w sezonie 1997/1998 i wtedy to osiągnął swój pierwszy sukces, jakim było zdobycie Pucharu Szwajcarii, natomiast w lidze Lausanne zakończyło sezon na 3. miejscu w tabeli. Podobnie było w 1999 roku, gdy zespół znów zajął miejsce na najniższym stopniu podium i po raz drugi z rzędu wywalczył krajowy puchar. Celestini grał w Lausanne jeszcze w sezonie 1999/2000 zdobywając wtedy wicemistrzostwo Szwajcarii.

Latem 2000 Celestini przeszedł do beniaminka francuskiej Ligue 1, Troyes AC. W lidze zadebiutował 28 lipca w przegranym 1:3 wyjazdowym meczu z Olympique Marsylia. Fabio był podstawowym zawodnikiem klubu, który w lidze spisywał się udanie i został rewelacją sezonu zajmując 7. miejsce i awansując do Pucharu Intertoto. W sezonie 2001/2002 awansował z niego do Pucharu UEFA, w którym zaszedł z Troyes do 2. rundy (porażka w dwumeczu z Leeds United), a w lidze ponownie zajął 7. pozycję.

W 2002 roku Celestini przeszedł do silniejszego Olympique Marsylia. Tam zadebiutował 10 sierpnia w wygranym 1:0 wyjazdowym meczu z AS Monaco. W Olympique pod wodzą Alaina Perrina zajął 3. miejsce w lidze i miał pewne miejsce w składzie na pozycji defensywnego pomocnika. W 2004 roku zajął z OM dopiero 7. pozycję oraz doszedł do finału Pucharu UEFA, w którym francuski zespół został pokonany 0:2 przez Valencię (w finale Celestini zagrał od 84. minuty, gdy zmienił Sylvaina N'Diaye).

W 2004 roku Celestini wyjechał do Hiszpanii i przez rok grał w tamtejszym Levante UD. W Primera División zadebiutował 12 września w wygranym 3:1 meczu z Racingiem Santander. Levante spadło jednak z ligi i szwajcarski pomocnik wrócił z wypożyczenia do Marsylii, ale ostatecznie za darmo odszedł do innego hiszpańskiego zespołu, Getafe CF. W 2006 roku zajął z tym klubem 9. miejsce. Rozegrał tylko 19 meczów, gdyż w drugiej połowie sezonu leczył kontuzję. W sezonie 2006/2007 awansował z Getafe do finału Pucharu Hiszpanii.