Родился 24 октября 1945 г. в г. Иванове в семье учителей Леонида Николаевича и Екатерины Андреевны Мартыновых.
В 1963 г. поступил в Москве в Государственный институт театрального искусства им. А. В. Луначарского (ныне Российский институт театрального искусства - ГИТИС). Со второго курса был призван в армию. Проходил срочную службу в войсках ПВО в Средней Азии. После демобилизации продолжил обучение в ГИТИСе. Окончил вуз в 1970 г., выпускник курса педагогов Варвары Вронской и Павла Хомского.
В 1970-1972 гг. Андрей Мартынов был актером Московского театра юного зрителя.
С 1972 по 1981 г. служил в Московском драматическом театре на Малой Бронной.
Широкую известность Андрею Мартынову принесла его первая роль в кино - старшина Федот Васков в экранизации военной повести Бориса Васильева "...А зори здесь тихие" (1972, режиссер Станислав Ростоцкий). Среди других работ: Кирьян Инютин в телесериале "Вечный зов" по роману Анатолия Иванова (1973-1983, Владимир Краснопольский и Валерий Усков), Кряквин в драме "Факты минувшего дня" по произведению Юрия Скопа "Техника безопасности" (1981, Владимир Басов), Гаврила Андреевич в экранизации повести Ивана Тургенева "Му-му" (1998, Юрий Грымов). Последняя роль к настоящему времени - Никанор в сериале "Сонька. Продолжение легенды" (2010, Виктор Мережко). В общей сложности актер снялся в 40 фильмах и сериалах.
Андрей Мартынов принимал участие в дублировании нескольких десятков иностранных кинокартин. В их числе: "Крестный отец" (1972, режиссер Фрэнсис Форд Коппола, США), "Ганди" (1982, Ричард Аттенборо, Великобритания - Индия), "Деревенька моя центральная" (1985, Иржи Менцель, Чехословакия), "Одиночка" (1986, Жак Дере, Франция), "Список Шиндлера" (1993, Стивен Спилберг, США), "Сонная лощина" (1999, Тим Бертон, США), "Двенадцать друзей Оушена" (2004, Стивен Содерберг, США).
Член Союза кинематографистов России.
Народный артист РФ (1994).
Лауреат премии Ленинского комсомола 1974 г., Государственной премии СССР в области литературы, искусства и архитектуры 1975 г., Государственной премии РСФСР им. братьев Васильевых 1982 г.
Разведен. Был женат на гражданке Германии Франциске Тун-Хоэнштайн (род. 1951, филолог-русист, литературовед). Сын - Александр (род. 1977, театральный художник).