Родился в 1727 г. в селе Позники Лубенского уезда Киевской губернии, происходил из малороссийских дворян сербского происхождения. По окончании образования в Киевской духовной академии начал службу в Малороссии и в 1747 г. уже получил звание бунчукового товарища; в 1749 г. определён поручиком и Лейб-компании гренадером.
Семилетняя война с Пруссией доставила ему случай явить первые опыты храбрости, и он приобрёл несколько чинов на поле чести, в сражениях при Пальциге, Кунерсдорфе и при осаде Кольберга. В 1771 г. Милорадович был бригадиром, когда началась война с Турцией; он сражался под знамёнами Румянцева и в первую же кампанию покрыл себя славой; с 1800 человек пехоты и 300 казаками переправился через Дунай и разбил при Мачине семитысячный турецкий корпус; Румянцев в донесении императрице Екатерине II писал о последнем сражении: «... генерал-майор Милорадович своими, сперва легкими действиями, служившими к обращению на себя внимания, одержал поверхность над неприятелем при городе Мачине, а 21-го числа, переправившись с корпусом на соротивной берег, атаковал неприятеля в его Мачинском лагере, и выгнав онаго, овладел городом, знатным числом пушек и всем тут бывшим снарядом». За это дело Милорадович был награждён орденом св. Анны 1-й степени а императрица Екатерина II даже сообщала о ней в письмах Вольтеру.
Героями сражения при Козлуджи в 1773 г. бесспорно следует считать Суворова, Озерова и Милорадовича; поражение турок было полное. В награду за войну 1771—1774 гг. Милорадович, между прочим, в день мирного торжества 10 июля 1775 г., в силу статуса, получил орден св. Георгия 3-й степени (№ 44)
Кроме того ему было пожаловано село Вороньки в Лубенском уезде.
В 1779 г. Милорадович был произведён в генерал-поручики и вскоре назначен правителем только что учреждённого Черниговского наместничества, которым управлял более пятнадцати лет и был единственным его управляющим, так как подобное наместничество существовало сравнительно недолго и было заменено учреждением Малороссийской губернии. В 1786 г. награждён орденами св. Владимира 2-й степени и св. Александра Невского; 5 мая 1789 г. произведён в генерал-поручики.
Мужественный на поле брани, Милорадович был справедливый и беспристрастный наместник, отличавшийся хлебосольством, о чём вспоминал в разговорах с его сыном Суворов, сблизившийся с Милорадовичем во время Турецкой войны.
В 1791 г. князь Потёмкин-Таврический, проезжая Чернигов, остановился у Милорадовича. На обеде в его честь, к которому съехались важнейшие лица города, Потёмкин рассказывал о своих военных действиях и победах; все слушали с большим вниманием, и лишь Милорадович заметил: «Ваши победы действительно замечательны и блистательны, но ведь и когда мы воевали, то побеждали, зато более щадили людей». Потемкин, не привыкший к возражениям, вспылил и, разбив ударом кулака тарелку, встал из-за стола, ушёл к себе в комнаты, не кончив обеда, и на другой день покинул Чернигов. Все встревожились за участь Милорадовича, но неприятность этим инцидентом окончилась.
Милорадович прилагал большие заботы об образовании сына Михаила, для чего отправил его в Кёнигсбергский и Гёттингенский университеты, а для усовершенствования в военных науках — в Мец и Страсбург. Михаил Андреевич был записан на службу в армейский полк; желая, чтобы он числился в гвардии, Милорадович, получив орден св. Александра Невского, просил императрицу Екатерину II вместо этой награды перевести сына в лейб-гвардии Измайловский полк; эта просьба была уважена, а вскоре Милорадовичу-старшему была пожалована и Александровская лента.
Расточительность сына неоднократно огорчала Андрея Степановича, и он, будучи крутого нрава, когда промотавшийся сынок, уже капитан гвардии, приехал в отпуск, встретил его при всех с распростёртыми объятиями, а затем пригласил в кабинет, где и высек, говоря, что наказывает не капитана гвардии императрицы, а своего блудного сына.
Милорадович был женат с 1768 г. на Марии Андреевне Горленко; кроме сына, знаменитого героя Наполеоновских войны Михаила Андреевича, у них была дочь — Мария Андреевна (умерла в 1851 г., замужем за Черниговским предводителем дворянства Николаем Михайловичем Стороженко).
Скончался 2 мая 1796 г. в Чернигове, погребён в Черниговском Елецком монастыре.
