Родился 18 октября 1940 года в городе Балашове в семье военнослужащего.
В 1962 году окончил Пензенский политехнический институт. Распределён в Калугу на завод «Калугаприбор», который выпускал оборудование для систем правительственной связи. Работал инженером, старшим инженером-настройщиком, заместителем начальника цеха.
В 1965 году вернулся в Пензу на предприятие «почтовый ящик 30/10» Министерства радиопромышленности СССР, в должности старшего инженера. В следующем, 1966 году, на базе этого предприятия был создан Пензенский научно-исследовательский электротехнический институт (ПНИЭИ) Министерства промышленности средств связи СССР, в котором он проработал следующие 20 лет. Сначала занимал должности старшего инженера, ведущего инженера, начальника лаборатории, начальника сектора. С 1976 года  занимал должности начальника научно-исследовательского отдела, заместителя директора института по научной работе.

С декабря 1982 года — первый заместитель Генерального директора Пензенского производственного объединения «Кристалл» по науке — директор ПНИЭИ. С февраля 1983 года — Генеральный директор Пензенского производственного объединения «Кристалл» Министерства промышленности средств связи СССР. Это предприятие было ведущим в стране по разработке закрытых систем связи. Производственную деятельность успешно сочетал с научной и преподавательской работой в Пензенском политехническом институте.
В мае 1986 года назначен заместителем начальника Управления войск правительственной связи по вопросам технического оснащения Комитета государственной безопасности. В том же году ему присвоено воинское звание генерал-майор (до этого был подполковником действующего резерва КГБ СССР). За время своей служебной деятельности внёс значительный вклад в обновление и перевооружение современной связной техникой органов и войск правительственной связи Российской Федерации. В мае 1988 года присвоено воинское звание генерал-лейтенант.
В августе 1991 года указом Президента СССР Михаила Горбачёва был создан Комитет правительственной связи при Президенте СССР, а Александр Старовойтов назначен председателем данного комитета.

Одним из первых решений Президента России Бориса Ельцина после распада СССР стала перестройка органов государственной безопасности. Указом Президента России № 313 от 24 декабря 1991 года на базе Восьмого главного управления КГБ СССР, Шестнадцатого управления КГБ СССР, Комитета правительственной связи при Президенте СССР, ряда научных и производственных организаций было создано Федеральное агентство правительственной связи и информации при Президенте Российской Федерации (ФАПСИ). Александр Старовойтов стал первым директором нового агентства. 12 февраля 1993 года ему присвоено воинское звание генерал-полковник.
ФАПСИ успешно справлялось с поставленными перед ним задачами. Указом Президента Российской Федерации Бориса. Ельцина от 23 февраля 1998 года Старовойтову присвоено воинское звание генерал армии.
В 1997 году окончил Высшие курсы Военной академии Генерального штаба Вооружённых сил РФ.

С 1995 года входил в состав Комиссии при Президенте России по Государственным премиям Российской Федерации в области науки и техники. Являлся председателем Межведомственной комиссии Совета Безопасности Российской Федерации по информационной безопасности, председателем Координационного совета по обеспечению безопасности шифровальных средств и их эксплуатации в системах правительственной и закрытой ведомственной связи государств — участников СНГ, а также был соучредителем Информационного агентства при Комитете по проведению военной реформы. Входил в состав Совета директоров АО «Ростелеком» и АО «Связьинвест». Член Совета Безопасности РФ с 18 ноября 1998 по 13 апреля 1999 года. В 1999 году уволен с военной службы в запас.
После увольнения с военной службы вернулся к научно-исследовательской и изобретательской работе в области закрытых систем связи и информации. С 2000 года был президентом ООО «ТехинформКонсалтинг».
Закрытым Указом Президента Российской Федерации от 17 августа 1999 года за руководство коллективом разработчиков государственной автоматизированной системы выборов Александру Старовойтову присвоено звание Героя Российской Федерации с вручением знака особого отличия — медали «Золотая Звезда».

С 2006 года по день смерти — директор Федерального государственного научного учреждения «Центр информационных технологий и систем органов исполнительной власти» (ФГНУ ЦИТиС) и Генеральный директор Международного центра по информатике и электронике «ИнтерЭВМ». С 2012 года — президент, с 2017 года и. о. президента Федерального государственного автономного научного учреждения «Центр информационных технологий и систем органов исполнительной власти» (ФГАНУ ЦИТиС) и Генеральный директор Международного центра по информатике и электронике «ИнтерЭВМ».

Был Генеральным конструктором автоматизированных систем передачи данных АСУ войсками фронта, Генеральным конструктором государственной системы конфиденциальной связи России, Генеральным конструктором специальной информационно-телекоммуникационной системы органов государственной власти. Руководил всем комплексом работ по созданию системы специального информационного обеспечения руководства страны. Под руководством Александра Старовойтова проведено большое количество специальных разработок с применением микропроцессорной техники, организовано их промышленное производство и внедрение, что обеспечило безопасность автоматизированных систем управления в широком диапазоне — от космоса до глубоководных объектов. Один из инициаторов разработки действующей Доктрины информационной безопасности Российской Федерации. Автор свыше 40 изобретений и свыше 150 научных трудов и публикаций.

Действительный член (академик), вице-президент и первый вице-президент общественной организации «Академия инженерных наук им. А. М. Прохорова». Действительный член (академик) общественных организаций: «Российская академия естественных наук» и «Академия электротехнических наук Российской Федерации». Был членом Клуба военачальников Российской Федерации.
Сочетал научно-практическую деятельность с педагогической работой, являясь заведующим базовой кафедрой вычислительных систем и сетей Российского технологического университета — «МИРЭА», заведующим кафедрой «Интеллектуальные информационные технологии и системы» Московского физико-технического института «МФТИ», заведующим кафедрой «Кибербезопасность» Национального исследовательского ядерного университета «МИФИ».
Являлся председателем Национального комитета содействия экономическому сотрудничеству со странами Латинской Америки, председателем Делового совета Россия-Чили, председателем Совета директоров и руководителем головной организации «Центра высоких технологий ЕврАзЭС».
Действительный член Академии криптографии Российской Федерации.
Ученая степень: профессор.
Скончался 17 июля 2021 года в Москве. Похоронен с воинскими почестями на Троекуровском кладбище (участок № 4).