Kolukanova fik sin olympiske debut som 19-årig ved Sommer-OL 2000 i Sydney, hvor hun deltog i kvindernes 50 m fritøj.
- Hvad? Hun nåede semifinalen ved at vinde svømmeturen mod Europamesteren Mette Jacobsen fra Danmark og Ana Belén Palomo fra Spanien. Hun satte en ny estisk rekord i to på hinanden følgende svømmelser, først i forløbet (25,96) og derefter i tre-personers svømmetur et par timer senere. Efterfulgt af en aftensession, sluttede Kolukanova sin semifinal run med en tid på 26,03, kun syv hundrededele af et sekund (0,07) ud over hendes rekord.