Ha iniziato la propria carriera da calciatore nelle file del Wimbledon FC. Nella stagione 1989-1990 è stato inserito nella rosa della prima squadra. Il debutto in First Division è avvenuto il 20 aprile 1991, in Aston Villa-Wimbledon FC (1-2)[3]. Nella seconda parte della stagione 1991-1992 ha giocato in prestito al Crystal Palace. Rientrato al Wimbledon FC nell'estate 1992, vi ha militato fino alla stagione 1999-2000, totalizzando 179 presenze e 254 reti subite in campionato. Il 27 maggio 2000 si è trasferito al Tottenham[4]. Il debutto ufficiale con gli Spurs è avvenuto il 19 agosto 2000, nell'incontro di campionato Tottenham-Ipswich Town (3-1)[5]. Ha militato nelle file degli Spurs per tre stagioni, totalizzando 64 presenze e 95 reti subite in campionato. Il 29 agosto 2003 si è trasferito al Chelsea[6][7]. Il 31 luglio 2004 si è trasferito a parametro zero al Leeds Utd[8], club militante nella seconda serie inglese. Ha militato nelle file dei Whites per tre stagioni, totalizzando 95 presenze e 105 reti subite in campionato. Il 23 novembre 2006 si è trasferito in prestito al Doncaster[9]. Il 15 maggio 2007 il Leeds Utd ha annunciato che il contratto di Sullivan, in scadenza, non sarebbe stato rinnovato[10]. Il 19 giugno 2007 è tornato a titolo definitivo al Doncaster[11]. Ha militato nel club biancorosso per cinque stagioni, totalizzando 177 presenze in campionato e 220 reti subite. Il 16 novembre 2012 si è trasferito in prestito all'AFC Wimbledon[12]. Rientrato dal prestito nel marzo 2013, ha militato nelle file del Doncaster fino al termine della stagione[13], terminando così la propria carriera da calciatore all'età di 43 anni.
Il 16 luglio 2013 è diventato è entrato nello staff delle giovanili del Leeds Utd[18][19], assumendo il ruolo di preparatore dei portieri. La stagione successiva ha svolto il ruolo di preparatore dei portieri per la prima squadra[20]. Il 9 giugno 2015, in seguito alla nomina di Richard Hartis quale nuovo preparatore dei portieri della prima squadra, Sullivan è tornato a svolgere il ruolo di preparatore portieri nello staff delle giovanili[21]. Ha mantenuto tale incarico fino al 2020, anno in cui è diventato preparatore dei portieri delle giovanili dell'Hull City[22]. Il 10 giugno 2024 si è dimesso[22].