Erste internationale Erfahrungen sammelte Andrei Tereschin im Jahr 2001, als er bei den Junioreneuropameisterschaften in Grosseto mit übersprungenen 2,11 m den sechsten Platz belegte. 2003 gewann er bei den U23-Europameisterschaften in Bydgoszcz mit 2,27 m die Silbermedaille hinter dem Polen Aleksander Waleriańczyk und anschließend belegte er bei der Sommer-Universiade in Daegu mit 2,20 m den sechsten Platz. 2005 gelangte er bei den Halleneuropameisterschaften in Madrid mit 2,24 m auf Rang acht und im August schied er bei den Weltmeisterschaften in Helsinki mit einer Höhe von 2,15 m in der Qualifikationsrunde aus. Im Jahr darauf gewann er bei den Hallenweltmeisterschaften in Moskau mit 2,35 m die Silbermedaille hinter seinem Landsmann Jaroslaw Rybakow und 2007 belegte er bei den Halleneuropameisterschaften in Birmingham mit 2,20 m den siebten Platz. Im August verpasste er bei den Weltmeisterschaften in Osaka mit 2,23 m den Finaleinzug, ehe er bei den Militärweltspielen in Hyderabad mit 2,26 m die Goldmedaille gewann. 2008 kam er bei den Hallenweltmeisterschaften in Valencia mit 2,24 m nicht über die Vorrunde hinaus und im Jahr darauf schied er bei den Weltmeisterschaften in Berlin mit derselben Höhe in der Qualifikationsrunde aus. 2012 beendete er dann seine aktive sportliche Karriere im Alter von 30 Jahren.
2006 wurde Tereschin russischer Hallenmeister im Hochsprung.