Родился в дворянской семье в городе Нарва, в 1883 поступил на историко-филологический факультет Московского университета. В 1884 в «Исследованиях по русскому языку» опубликована первая его статья «Исследования о языке новгородских грамот XIII и XIV вв».
Ученик Ф. Ф. Фортунатова. Впервые замечен в серьёзных научных кругах после выступления во время защиты А. И. Соболевским его магистерской диссертации — о системе фонем праславянского языка. Шахматов выступил с убедительной критикой некоторых важных положений доклада, чем вызвал сильную неприязнь уже известного в ту пору научными трудами Соболевского. Напряжённые отношения ученых сохранялись до конца жизни Шахматова.
В 1887 защитил диссертацию на тему «О долготе и ударении в общеславянском языке», после окончания университета остался при нём и к 1890 стал приват-доцентом.
В 1890 году Алексей Александрович начал читать курс истории русского языка в Московском университете. Однако едва приступив к преподавательской деятельности, А. А. Шахматов принял неожиданное для коллег-филологов решение оставить науку и уехать к родственникам в саратовскую деревню. Уже из Саратова в одном из писем Фортунатову Шахматов признаётся, что заинтересовался современным крестьянским управлением и теперь полагает всю свою душу в работе на благо окружающего его сельского населения.
1 июля 1891 года Шахматов официально вступил в должность начальника земской управы и в течение двух лет активно участвовал в хозяйственной жизни вверенного ему уезда. Во время эпидемии холеры весной 1892 года содействовал организации медицинской помощи, хлопотал о командировании в волость нескольких сестёр милосердия и фельдшеров.
В том же 1892 году А. А. Шахматов возобновил работу над магистерской диссертацией, а в 1893 году по приглашению председателя Отделения русского языка и словесности Петербургской Академии наук академика А. Ф. Бычкова принял звание адъюнкта Академии и вернулся к научной деятельности.
В 1894 выдвинул свою работу «Исследования в области русской фонетики» на соискание степени магистра, однако ему была присуждена высшая степень доктора русского языка и словесности.
Первые научные разработки — в области диалектологии. Совершил две экспедиции в середине 80-х гг. — в Архангельскую и Олонецкую губернии.
После смерти Я. К. Грота взял на себя составление первого нормативного словаря русского языка.
С 1894 адъюнкт Петербургской АН, с 1898 — член Правления Академии наук, самый молодой за всю историю её существования (34 года), с 1899 — действительный член АН. С 1910 профессор Петербургского университета.
С 1906 — член Государственного совета от академической курии. Участвовал в подготовке реформы русской орфографии, осуществленной в 1917—1918.
Член Сербской Академии наук (1904), доктор философии Пражского университета (1909), доктор философии Берлинского университета (1910), член-корреспондент Краковской Академии наук (1910), почётный член Витебской учёной архивной комиссии и др.
Умер от истощения в Петрограде в августе 1920 года. Похоронен на Волковском кладбище.
После смерти ученого в 1925—1927 был издан его во многом нетрадиционный «Синтаксис русского языка», оказавший значительное влияние на развитие синтаксической теории в России. В нем Шахматов впервые сделал попытку выявить систему в огромном разнообразии синтаксических конструкций русского языка.
Об учёном его сестрой — Е. А. Шахматовой-Масальской — оставлены мемуары.
После работ Шахматова любое исследование по истории древней Руси опирается на его выводы. Учёный заложил основы текстологии как науки.
Особенно большой вклад исследователь внёс в разработку текстологии древнерусского летописания, в частности — «Повести временных лет». Сличение различных редакций данного памятника позволило Шахматову прийти к выводу о том, что дошедший до нас текст по происхождению многослоен и имеет несколько стадий формирования. Логические нестыковки, текстовые вставки, разрывающие связный текст, отсутствующие в Новгородской Первой летописи, по мысли Шахматова, являются свидетельством существования гипотетического Начального свода, созданного приблизительно в 90-х гг. XI века. Например, в тексте Новгородской Первой летописи отсутствуют договоры Руси с греками X века, а также все прямые цитаты из греческой Хроники Георгия Амартола, которой пользовался составитель Повести временных лет. При дальнейшем изучении Начального свода А. А. Шахматов обнаружил другие логические несоответствия. Из этого делался вывод о том, что в основе Начального свода лежала какая-то летопись, составленная между 977 и 1044 гг. Её исследователь назвал Древнейшим сводом.
Под руководством Шахматова Отделение русского языка и словесности Императорской Академии наук стало центром отечественной филологии. По инициативе Шахматова Академия наук издала монографии, словари, материалы и исследования по кашубскому, полабскому, лужицкому, польскому, сербскому, словенскому языкам. В 1897 Шахматов возглавил работу над академическим словарем русского языка. Участвовал в подготовке реформы русской орфографии, осуществленной в 1917—1918.
Выводил восточнославянские языки от «общедревнерусского» языка, дезинтеграция которого, по его мнению, началась уже в VII ст., но была задержана интеграционными процессами, связанными с государственным единством в рамках Киевской Руси
Алексей Шахматов — один из авторов работы «Украинский народ в его прошлом и настоящем» (1916) , принимал участие в написании декларации Петербургской АН «Про отмену ограничений малорусского печатного слова» (1905—1906), автор подробных рецензий на грамматики украинского языка А. Крымского и С. Смаль-Стоцкого, словарь украинского языка Б.Гринченко.
Алексей Александрович с интересом и сочувствием относился к развитию украинской литературы и украинского языка, но скептически высказывался по отношению к стремлению деятелей «украинского движения» к отделению малорусской народности от единого русского народа, по великорусским этнографическим представлениям того времени подразделявшегося на белорусов, великороссов и малороссов.
Шахматов, в отличие от других русских филологов — Соболевского, Флоринского, Ягича, Корша и др. видел причиной стремления части украинской интеллигенции к обособлению не идейные и политические аспекты, а реакцию на запретительные меры по отношению к украинскому языку.