Tsybulskaja käveli Göteborgin MM-kisoissa 1995 kahdenneksitoista 10 kilometrin kävelyssä ajalla 43.34. Kaksi vuotta myöhemmin hän oli samalla matkalla kävelyn maailmancupissa yhdestoista ajalla 42.54 ja voitti Ateenan MM-kisoissa 10 000 metrin ratakävelyssä MM-pronssia ajalla 43.49,24. Vuonna 1999 hän sijoittui kävelyn maailmancupissa 20 kilometrin kävelyssä kahdenneksikymmenenneksiviidenneksi käveltyään 1.33.14. Sydneyn olympialaisissa 2000 hän oli matkan kahdeskymmeneskahdeksas, mutta seuraavana vuonna Edmontonin MM-kisoissa hän voitti MM-hopeaa ajalla 1.28.49. 2002 hän käveli kävelyn maailmancupissa seitsemänneksi ja voitti Pariisin MM-kisoissa 2003 MM-pronssia ajalla 1.28.10. Vuonna 2004 hän sijoittui kävelyn maailmancupissa kolmanneksikymmenenneksiseitsemänneksi ja Ateenan olympialaisissa viidenneksitoista.