Предки Столетовых были выходцами из Новгорода Великого, высланные в ХV в. во времена Ивана III и осевшие во Владимире. Дмитрий Акимович Столетов (1734 - 1794) имел мастерскую по выделке кож, которая находилась «на берегу речки Лыбеди, переходя через оную с дороги, лежащей от Воскресенской церкви между городских земляных валов к Ивановскому мосту налево…». Им построен ныне существующий двухэтажный каменный дом, где не только жила семья Столетовых, но были склады, сдавались в наем комнаты.

Отец Александра и Николая Столетовых Григорий Михайлович был человеком очень сдержанным, замкнутым, неразговорчивым. Некоторые черты характера отца – сдержанность, нелюбовь к чувствительным излияниям и громким словам, подчеркнутую вежливость, постоянную корректность – унаследовал сын Александр.

Мать Александра Васильевна (1806 - 1889), отдавала себя занятиям домашним хозяйством и воспитанием детей. Преподавала детям арифметику и русский язык. Она относилась к ним с большой нежностью, и они платили ей тем же. В старости она с тревогой говорила: «Что-то там мои мальчики?» - Хотя «мальчикам» было уже за пятьдесят.