Stepanov maakte in 1999 voor het eerst zijn opwachting bij de nationale ploeg van Estland. Onder leiding van de IJslandse bondscoach Teitur Thórdarson maakte hij zijn debuut op 30 oktober1999 in de vriendschappelijke uitwedstrijd tegen Irak (0-1) in Abu Dhabi. Stepanov kwam tot een totaal van 88 interlands en één doelpunt.