Александр Бухштаб родился в Ставрополе, в семье городового врача, акушера и гинеколога Абрама Хаскелевича (Адольфа Александровича) Бухштаба (1862, Одесса — ), выпускника Императорской медико-хирургической академии. Учился в Ростовском государственном университете, по его окончании поступил на факультет математики в Московский государственный университет, в 1928 году получил степень доктора философии по математике. Работал в Азербайджананском универстете на кафедре алгебры и деканом по физике и математике.
В 1939 году Бухштаб защитили кандидатскую дессертацию под руководством Александра Хинчина, через некоторое время был назначен преподавателем в Московском государственном университете. Когда началась война переезжает в Азербайджан для работы преподавателем в Азербайджананском государственном универстете.
В 1943 году защитил диссертацию по математике в Математическом институте им. В. А. Стеклова.
До конца жизни остался преподавателем в Московском педагогическом государственном университете, в котором он обучал студентов, среди них есть двое известных учеников Григорий Фрейман и Илья Пятецкий-Шапиро.Двоюродный брат — литературовед Борис Яковлевич Бухштаб.