1977-1979-cu illərdə Silahlı Qüvvələrdə xidmət etmişdir.

Milis idarəsində 1980-ci ildən Minskdə binaların, obyektlərin, Dövlət Bankı müəssisələrin mühafizəsi alayının milisioneri kimi xidmətə başlamışdır.

1986-cı ildə SSRİ DİN-in Minsk ali məktəbini, 1992-ci ildə SSRİ DİN Akademiyasını (indiki Belarus Respublikası DİN-in Akademiyası). Hüquq-mühafizə fəaliyyətinin təşkili, hüquqşünaslıq ixtisası üzrə təhsil.alıb.

SSRİ DİN-in Minsk ali məktəbini bitirdikdən sonra Minskin Lenin rayonunun yetkinlik yaşına çatmayanların işləri üzrə müvəkkili işlədi. 1992-ci ilin noyabrından kriminal milis şöbəsinə rəhbərlik edib.

1995-ci ilin mart ayında Minsk şəhəri Daxili İşlər İdarəsinin cinayət axtarışı idarəsinin rəis müavini təyin edilib.

1996-cı ildən 1998-ci ilədək paytaxtın Zavodskoy rayonunun daxili işlərinə idarə edilməsinə rəhbərlik etmişdir. 1998-dən 2001-dək Frunzen rayonunun Rayon Daxili İşlər İdarəsinə rəhbərlik edib.

2003-cü ilin iyununda Kuleşova "milis general-mayoru" xüsusi rütbəsi verilmişdir. 2 iyul 2003-cü il 281 saylı prezident fərmanı ilə Minsk şəhəri daxili işlər idarəsinin rəisi təyin edildi. 29 avqust 2008-ci ildə Belarusun ictimai təhlükəsizlik milisinin rəisi və daxili işlər nazirinin müavini təyin olundu.

2008-ci il dekabrın 5-də daxili işlər nazirinin birinci müavini və Belarus Respublikası DİN kriminal milisi təyin olunmuşdur.

2009-cu il aprelin 6-da daxili işlər nazirinin vəzifəsini müvəqqəti icra edirdi, bu hadisə daxili işlər naziri Vladimir Naumovun səhhətinə görə istefasından sonra baş verdi).

2 iyun 2009-cu ildə Belarus Respublikasının Prezidenti A.Lukaşenko general-mayor Anatoli Niloviç Kuleşova 280 saylı Fərmanı İlə milis nazirinin birinci müavini vəzifəsindən azad etməklə ölkənin daxili işlər naziri təyin etdi.

2011-ci il fevralın 22-də Prezident fərmanı ilə milis general-mayoru Kuleşova növbəti milis general-leytenantı xüsusi rütbəsi verildi.

• 2007-06-28 at the Wayback Machine (rusca)
• (rusca)

1. . 2016-03-04 tarixində arxivləşdirilib. İstifadə tarixi: 2017-07-01.