Родился в дворянской семье Шахматовых Саратовской (Кумышской) ветви. Отец — Александр Алексеевич Шахматов, чиновник, юрист. Мать — Мария Фёдоровна, урождённая Козен. У Алексея Шахматова были три сестры: одна сводная — Наталья Александровна и две единоутробных — Евгения (в замужестве Масальская) и Ольга. Родители в 1871 году умерли, и троих малолетних детей, Евгению, Алексея и Ольгу, взял на воспитание в свою семью дядя Алексей Алексеевич Шахматов. Поэтому некоторое время Алексей жил в деревне Губаревке Саратовской губернии, где с ним занимался дядя, некогда закончивший Гейдельбергский университет.
В 1874—1878 годах учился в гимназии Креймана, затем перешёл в 5-й класс 4-й московской гимназии. Ещё в 1878 году, гимназистом, написал статью о происхождении языков и представил её профессорам Императорского Московского университета В. Ф. Миллеру, Н. И. Стороженко и Ф. Ф. Фортунатову. Именно Фортунатов пригласил Шахматова в 1882 году на защиту А. И. Соболевским магистерской диссертации, посвящённой системе фонем праславянского языка, где Шахматов выступил с убедительной критикой некоторых важных положений доклада, вызвав сильную долголетнюю неприязнь Соболевского.
В гимназии Шахматов увлекался коллекционированием слов. В письмах домой он замечал: «Если Вам интересно, можете посмотреть на мой филологический бюджет за эту неделю, т.-е. приход и расход: у отца ученика 4-го класса я купил за 50 санскритских слов и за 3 готских слова — 60 исландских. За 40 персидских слов и 8 арабских — 50 финских и литовских. У дяди ученика 3-го класса я купил за 257 древнегерманских слов — 60 редких готских слов. За 641 санскритское — еврейскую азбуку и готские спряжения и склонения. За 70 кельтских — 340 санскритских, ещё не всех выданных.»
Окончив гимназию с серебряной медалью, в 1883 году поступил на историко-филологический факультет Императорского Московского университета. В 1884 году в «Исследованиях по русскому языку» была опубликована первая статья: «Исследования о языке новгородских грамот XIII и XIV вв.».
К моменту окончания университета в 1887 году подготовил выпускное кандидатское сочинение на тему: «О долготе и ударении в общеславянском языке». Оставлен при университете для приготовления к профессорскому званию по кафедре русского языка и словесности. В 1890 году, сдав магистерский экзамен, получил звание приват-доцента и начал читать курс истории русского языка в Императорском Московском университете. Однако, едва приступив к преподавательской деятельности, Шахматов принял неожиданное решение оставить науку и уехать к родственникам в саратовскую деревню. Уже из Саратова в одном из писем к своему учителю Ф. Ф. Фортунатову Шахматов признался, что заинтересовался современным крестьянским управлением и теперь полагает всю свою душу в работе на благо окружающего его сельского населения. Для этого 1 июля 1891 года он занял должность земского начальника и в течение двух лет активно участвовал в хозяйственной жизни уезда. Во время эпидемии холеры весной 1892 года содействовал организации медицинской помощи, хлопотал о командировании в волость нескольких сестёр милосердия и фельдшеров.