Окончил механико-математический факультет МГУ в 1954 году. Ученик Алексея Ляпунова.
До начала 1950-х годов в СССР не существовало специальности «программист», Ершов оказался одним из первых программистов, имевших специальное образование. После окончания аспирантуры механико-математического факультета в 1957 году возглавил отдел теоретического программирования Вычислительного центра АН СССР.
Вскоре после окончания МГУ становится руководителем работ и автором одной из первых программирующих программ для отечественных ЭВМ — БЭСМ и «Стрела». В 1958 году опубликовал монографию «Программирующая программа для быстродействующей электронной счетной машины», которая сразу же была издана за рубежом.
В 1960 году переехал в Новосибирский Академгородок, с которым была связана вся последующая научная и педагогическая деятельность.
Под его руководством и при его участии были созданы такие языки программирования, как Альфа, Альфа-6 и трансляторы с них.
С 1966 по 1972 год руководил созданием программно-аппаратной системы разделения времени АИСТ («автоматическая информационная станция») в СО АН СССР.
В 1970-е годы разработал типовую, общую для многих языков схему трансляции, пригодную для создания фрагментов оптимизированных трансляторов. Эта схема охватывала многие задачи автоматизации программирования: анализ свойств программ, систем преобразования программ, разработки входных языков, разработки оптимизирующих трансляторов. Для решения этой проблемы требовался специальный язык, чтобы на нём можно было описать все возникающие проблемы. Такой универсальный программирующий процессор и его внутренний язык описания был создан и получил название «Бета».
В 1981 году на 3-й Всемирной конференции Международной федерации по обработке информации и ЮНЕСКО по применению ЭВМ в обучении в Лозанне (Швейцария) делает доклад под названием «Программирование — вторая грамотность». Название доклада быстро становится лозунгом. В Новосибирске начинаются эксперименты по преподаванию программирования, а затем и информатики школьникам. Разрабатывается компьютер Агат, обучающая система «Школьница» и язык «Рапира». В 1985 году Ершовым совместно с группой соавторов был выпущен школьный учебник «Основы информатики и вычислительной техники» (ОИВТ) и началось преподавание информатики как учебного предмета во многих школах Советского Союза. Для записи алгоритмов в этом учебнике применялся алголоподобный язык, так называемый Русский алгоритмический язык (или Учебный алгоритмический язык), в шутку называемый «Ершол». Реализацией этого языка стал Е-практикум, разработанный на механико-математическом факультете МГУ.
С апреля 1987 года был председателем Научного совета АН СССР по комплексной проблеме «Кибернетика». Активно участвовал в создании отраслевого журнала «Микропроцессорные средства и системы».
Андрей Петрович Ершов умер после тяжелой болезни в Москве 8 декабря 1988 г.