Lesin begann 1984 mit dem Boxen und wurde während seiner Laufbahn fünffacher russischer Meister. Bei den russischen Meisterschaften 2001 unterlag er im Finale Alexander Powetkin, konnte ihn 2003 aber schlagen.
Bei beiden Olympischen Spielen, an denen er teilnahm, ging er als einer der Favoriten in das Turnier, konnte die Erwartungen jedoch nicht erfüllen. 1996 nahm er für Russland an den Olympischen Spielen in Atlanta teil. Dort besiegte er im Viertelfinale erneut René Monse, unterlag im Halbfinale aber dem späteren Sieger Wladimir Klitschko nach Punkten und sicherte sich damit eine Bronzemedaille.
Die Olympischen Spiele 2000 endeten für Lesin schon im ersten Kampf, als er vorzeitig gegen den späteren Goldmedaillengewinner Audley Harrison unterlag. Er hatte bis kurz vor Schluss nach Punkten vorn gelegen.
Vier Mal nahm Lesin an den Militärweltmeisterschaften teil, wobei er 1994 und 1999 die Goldmedaille gewann, 1995 im Finale gegen Vitali Klitschko verlor und 2002 im Halbfinale gegen Roberto Cammarelle, Italien, ausschied.