Aleksandrov speelde in totaal zes officieuze interlands (vijf doelpunten) voor het Moldavisch voetbalelftal in de periode 1992-1998. Hij maakte zijn debuut op 20 mei1992 in de vriendschappelijke interland tegen Litouwen (1-1), en scoorde daarin een keer. In zijn volgende interland, op 18 augustus1992 tegen Pakistan (5-0) tijdens het Jordanië Toernooi, trof hij viermaal doel. Het openingsdoelpunt in die wedstrijd kwam op naam van Alexei Scala.
