Воспитывался в артиллерийском кадетском корпусе (Второй кадетский корпус?), по окончании курса в котором, в 1756 году был выпущен в артиллерию штык-юнкером.
Принимал участие в русско-турецкой войне 1768—1774 годов; 30 апреля 1772 года за отличие был произведён в подполковники Московского легиона, где он после перевода легиона во II армию командовал I-м мушкетёрским батальоном; 26 ноября 1775 года награждён орденом Св. Георгия 4-й степени (№ 223 по кавалерскому списку Судравского и № 270 по списку Григоровича — Степанова).
За храбрые и мужественные подвиги, оказанные в турецкую войну 7 и 21 июля 770 года и во время десанта, сделанного неприятельскими войсками на Крымские берега.
Затем служил в Днепровском пехотном полку. Женился на Анне Васильевне Чертковой (1760 — 1796), дочери воронежского и харьковского генерал-губернатора В. А. Черткова.
В 1777 году А. Я. Леванидов был произведён в полковник, в 1782 — в бригадиры, в 1783 году получил в командование Полтавский пикинёрный (легко-конный) полк.
В 1784 году Леванидов получил чин генерал-майора; в 1785 году был шефом Стародубского карабинерного полка; с 1787 года командовал 2-й кавалерийской бригадой (куда входили Стародубский и Киевский карабинерные полки) и на этой должности в 1787—1791 годах вновь сражался с турками; за отличие в 1791 году был произведён в генерал-поручики и назначен командиром корпуса в Украинской армии, во главе которого с 1792 года находился в Речи Посполитой, участвуя в делах с конфедератами: «3 июня разбил неприятеля при Вишнеполе, затем участвовал в сражениях при Любаре, (12 июня), когда содействовал поражению Иосифа Понятовского, при Владимире (26 июня) и при Дубенке (2 июля)»; был награждён золотой шпагой, украшенной алмазами. В 1793 году получил от польского короля орден Белого орла и орден Св. Станислава.