Отец Ефим Павлович Зельдович, мать Алла Гербер — писательница, политический и общественный деятель, правозащитница.
Учился в средней физико-математической школе № 2 (ныне — лицей «Вторая школа»). В 1980 году окончил психологический факультет МГУ. Работал психологом в медицинских учреждениях Москвы.
Затем поступил на Высшие курсы сценаристов и режиссёров (мастерские Глеба Панфилова и Александра Митты, работу с актёром преподавал Анатолий Васильев), которые окончил в 1986 году. Снял короткометражные фильмы «Прогулка по городу» (1983), «Мальва» (1984), «Воительница» (1986).
С 1986 года — режиссёр-постановщик киностудии «Мосфильм».
В большом кино дебютировал в 1990 году с картиной «Закат» — фантазией на темы Исаака Бабеля. Фильм демонстрировался во внеконкурсной программе многочисленных фестивалей, а также на МКФ в Берлине (участие в Программе «Forum»).
В начале 90-х учился режиссуре и продюсированию в Европейской киноакадемии (Берлин) по гранту «Nipkow Programm».
В 1991—1993 годах работал над сценарием фильма «Шагал» совместно с Фридрихом Горенштейном. Проект не был реализован.
В конце 1990-х вместе с поэтом Аркадием Драгомощенко основал в Петербурге ежегодный философский семинар «Воды и Песка».
В 2000 году А. Зельдович представил свой фильм «Москва» по сценарию, написанному в соавторстве с Владимиром Сорокиным. Картина, ставшая событием российского кино, участвовала в официальной программе МКФ в Венеции и многих других международных кинофестивалях и удостоена премий в различных номинациях.
В феврале 2003 года А. Зельдович дебютировал как театральный режиссёр, осуществив вместе с художниками AES+F на сцене Центра им. Вс. Мейерхольда постановку спектакля «Отелло» по одноимённой пьесе У. Шекспира. События пьесы были перенесены в наши дни, в ней остались лишь главные действующие лица — Отелло, Дездемона, Эмилия и Яго.
Премьера картины «Мишень» (2011), также созданной по сценарию в соавторстве с Владимиром Сорокиным, состоялась на МКФ в Берлине. В дальнейшем фильм был показан на множестве международных фестивалей, был удостоен Гран-при на фестивале фантастического кино в Фантаспоа (2011), удостоен национальной премии кинокритики и кинопрессы «Белый слон» в трёх номинациях.
Последний фильм "Медея" был премирован на международном фестивале в Локарно, на национальном Российском фестивале Кинотавр, получил 2 премии критики "Белый Слон", в шорт листе на пять номинаций премии Национальной Кинакадемии "Ника"
Начиная с полнометражного кинофильма «Закат», Зельдович плодотворно сотрудничает с композитором Леонидом Десятниковым. Саундтрек «Москвы» был удостоен Гран-при на Бьеннале киномузыки в Бонне (2002).
В 2011−2012 годах преподавал режиссуру кино на факультете режиссуры, кино и телевидения в Институте современного искусства в Москве.
В 2017 - 2018 преподавал кионорежиссуру в Школе Дизайна Высшей Школы Экономики в Москве.
Летом 2016 года совместно с художниками AES+F поставил в Электротеатре Станиславский спектакль «Психоз» по пьесе Сары Кейн.
