Через два месяца команда одержала свою первую победу, проведя 13.03.1875 матч против местной регбийной команды «Астон Брук Сент-Мэри» (Aston Brook St Mary’s), основанной молодыми воспитанниками воскресной школы одноименной церкви в районе Астон Брук. По достигнутой договоренности первую половину матча на Уилсон Роуд играли по правилам регби, а вторую – по футбольным «Шеффилдским правилам». Матч завершился со счетом 1:0, а первый в истории клуба гол был забит Джеком Хьюзом.

Вот имена тех 15 человек, вышедших тогда на поле в составе «Астон Виллы»: Уильям Скэттергуд, Джордж Мэттьюз, Уолтер Прайс (капитан), Уильям Мэйсон, Джек Хьюз, Уильям Уайсс, Эдвард Ли, Фрэд Найт, Чарльз Миджли, Уильям Сач, Харолд Мэттьюз, Уильям Сотерс, Джордж Пэйдж, Альфрэд Роббинс, Харри Уотели.

Первые два года команда играла в синих рубашках с узкими поперечными красными полосками, белых шортах и синих гольфах, следующие два года – в белых рубашках с узкими поперечными черными полосками, белых шортах и черных гольфах, в 1879–1880 годах футболки стали черными, а на груди появился красный лев. Позже цвета и дизайн формы неоднократно менялись и лишь с 1887 года команда стала играть в привычных бордово-голубых футболках различной модификации. На эмблеме клуба изображён золотой лев, стоящий на задних лапах, на голубом фоне, с девизом «Prepared» («Готов»).

Первое время «Астон Вилла» выступала на лугах «Астон Парка» (1874–1876), после чего перебралась на загородный стадион «Перри Барр» (1876–1897).

К концу 70-х годов XIX века «Астон Вилла» стала одной из сильнейших команд в Мидленде. В 1880 году был выигран кубок Бирмингема – первый трофей в истории клуба, в том же сезоне команда начала выступления в Кубке Англии, где дошла до третьего раунда. Дебютный кубковый матч против клуба «Стаффорд Роуд Уоркс» состоялся 13.12.1879 и завершился со счетом 1:1. А 27 сентября того же года на стадионе «Мунтц Стрит» был проведен первый матч исторических соперников – «Астон Виллы» и «Бирмингем Сити», называвшегося тогда «Смолл Хилл». Матч закончился победой «Смолл Хилл» (1:0).

В сезоне 1880/1881 «Астон Вилла» выиграла 21 матч из 25, а также стала победителем Кубка Стаффордшира. В составе команды тогда выступали Джордж Копли, Артур Браун, Уильям Самьюэл Кросслэнд, Элайша Дэвис, Эндрю Хантер, Арчи Хантер, Самьюэл Лоу, Эдвард Боттерилл Ли, Томас Пэнк, Генри Ричмонд Симмондс, Говард Воотон, Уильям Уоттс и др. 18.02.1882 Артур Альфрэд Браун и Говард Воотон стали первыми представителями «Астон Виллы» в сборной Англии.

В первой половине 80-х годов XIX века «Астон Вилла» продолжала оставаться сильнейшей командой Мидленда, выиграв пять из шести розыгрышей Кубка Бирмингема. Первый большой национальный успех пришёл к клубу в 1887 году, когда впервые был выигран Кубок Англии. Финальный поединок против клуба «Вест Бромвич Альбион» состоялся 02.04.1887 на стадионе «Кеннингтон Овал» и завершился со счетом 2:0. Голы у победителей забили капитан команды Арчибальд («Арчи») Хантер (шотландец отличился во всех кубковых матчах «Астон Виллы» этого розыгрыша) и форвард сборной Англии Деннис («Денни») Ходгеттс. Интересно, что в полуфинале «Астон Вилла» со счетом 3:1 переиграла шотландский «Рейнджерс» из Глазго, который принимал участие в этом розыгрыше Кубка ФА.

За победителей в финале играли: Джеймс («Джимми») Уорнер, Фрэнк Култон, Джозеф Симмондс, Джон Генри Бартон, Гарри Р. Йетс, Фредерик Генри Герберт Доусон, Альберт Артур Браун, Арчи Хантер (первая суперзвезда в истории клуба, кумир фанатов викторианской эпохи), Оливер Говард Воотон, Деннис Ходгеттс.

Тренировал «бирмингемских львов» уроженец Глазго Джордж Баррелл Рэмзи, который в 1874–1882 годах играл за «Астон Виллу» в нападении или на краю полузащиты (одновременно, вплоть до 1884 года, работая в меднолитейной мастерской) и был капитаном команды. Как полагают многие исследователи истории английского футбола, именно Рэмзи и Хантер первыми в Англии стали культивировать игру в пас, прививать революционный комбинационный стиль. В июне 1882 года Джордж Рэмзи получил серьезную травму и был вынужден завершить карьеру игрока.

В 1884 году Джордж Рэмзи был назначен секретарём клуба, осуществляя примерно те же функции, что и современные главные тренеры. Рэмзи возглавлял «Астон Виллу» на протяжении 42 лет, до 1926 года, и этот период по-праву считается «золотой эрой» в истории клуба. Позже Рэмзи был почётным советником и вице-президентом клуба. На его могильной плите написано: «Основатель «Астон Виллы».

В 1888 году по инициативе президента клуба «Астон Вилла» Уильяма Макгрегора была основана первая Футбольная лига в мире. Дебютный лиговый матч сезона 1888/1889 бирмингенцы провели 08.09.1888, завершив поединок против «Вулверхэмптона» с мирным счетом 1:1. Уже в первом лиговом сезоне «Астон Вилла» становится вице-чемпионом Англии (впереди с отрывом в 11 очков оказался только «Престон Норт Энд»). Альберт Артур Аллен, забив в 21 матче 17 голов, становится лучшим бомбардиром «Астон Виллы» в этом сезоне (3-й результат в турнире первого дивизиона). Забив 29.09.1888 три мяча в ворота «Ноттс Каунти», Аллен стал автором первого хет-трика в истории Футбольной лиги. Мало того, Аллен и автор первого хет-трика в истории сборной Англии. 07.04.1888, в своем единственном матче в составе национальной команды (против Ирландии) он забил три гола.

В составе первых вице-чемпионов Англии кроме Аллена играли: Джеймс Уорнер, Уолтер Уильям Эшмор, Альберт Браун, Джон Бартон, Фрэнк Култон, Гершом Кокс (автор первого автогола в истории Футбольной лиги), Фредерик Доусон, Гарри Персивал Дэви, Артур Альберт Диксон, Бэтти Гэрви, Арчи Гудолл (брат форварда «Престона» Джона Гудолла – лучшего бомбардира первого английского чемпионата; потом они долгие годы будут играть вместе за «Дерби Каунти»), Томми Грин, Томас Гаррисон, Деннис Ходгеттс, Арчи Хантер, Роберт Самьюэл Томас, Артур Уилберт Уолластон, Гарри Йетс.

После этого в игре команды наступил спад, и в двух следующих сезонах она заняла лишь 8-е и 9-е места. Сезоны 1891/1892 и 1892/1893 «Астон Вилла» завершила на 4-м месте. В сезоне 1891/1892 «Астон Вилла» во второй раз добралась до финала Кубка Англии, где её, опять же во второй раз, поджидал «Вест Бромвич Альбион», который и победил со счетом 3:0. Вскоре у «бирмингенских львов» появится хороший шанс взять реванш…

В сезоне 1893/1894 «Астон Вилла» первые в своей истории становится чемпионом Англии. Команда одержала 19 побед, 5 матчей проиграла и 6 завершила вничью. 84 гола было забито и ровно в два раза меньше (42) пропущено. В составе чемпионов играли: Уильям («Вилли») Даннинг (28 матчей), Уильям Чарльз («Чарли») Атерсмит (25 матчей, 10 голов), Джон Бэйрд (29), Уильям Гровс (22/3), Джимми Коуэн (30/3), Джон («Джек») Рейнолдс (26/7), Деннис Ходгеттс (29/12), Джон Генри Джордж («Джек») Дэви (29/20), Уильям Уилфорд (19), Альберт Вулли (14/8), Стивен Смит (15/2), Роберт («Боб») Чэтт (13/5), Джеймс Эллиотт (12), Чарльз Бойд Хэйр (10/7), Альберт Браун (6/2), Джеймс («Джимми») Логан (4/1), Джордж Фрэнк Бартон (4), Джордж Расселл (5), Уильям Дэви (4), Джеймс («Джимми») Джеймс Стэнли Джиллан (3), Лу Бенуэлл (1), Фрэнк Култон (1), Уолтер Рэндл (1).

Это было началом безоговорочного доминирования клуба в Англии. За последующие шесть сезонов «Астон Вилла» еще четыре раза выиграла чемпионат страна (1896, 1897, 1899, 1900) и дважды Кубок Англии (в 1895 году со счетом 1:0 был побежден «Вест Бромвич Альбион, а в 1897 – «Эвертон» со счетом 3:2).