Aston Villa var naturligvis med som en af de 12 grundlæggere af The Football League i 1888, men klubbens historie begyndte faktisk tidligere med de fire personer Jack Hughes, Frederick Matthews, Walter Price og William Scattergood. Det var denne kvartet fra kricketholdet ved kirken Villa Cross Wesleyan, som i 1874 mødtes under gas-lampens skær på Heathfield Road for at stifte en ny klub.
De havde været på udkig efter en sportsgren, der kunne holde dem beskæftigede om vinteren og havde kastet deres opmærksomhed på det herlige spil, fodbold, efter at have overværet en hastigt improviseret kamp på en græsmark ved Heathfield Road.
Den netop grundlagte klub, Aston Villa, fik sin debut mod Aston Brook St. Mary's i 1874 i en usædvanlig kamp. Modstanderen var nemlig et rugbyhold, så første halvleg blev spillet efter rugbyreglerne, mens anden halvleg var efter fodboldforbundets reglement. Til historien hører, at Villa vandt 1-0 på et mål af Jack Hughes. Villa fik sin første rigtige hjemmebane i 1876, hvor Perry Barr blev lejet på en 3-års aftale med en årlig leje på £7 det første år, stigende til £15 og £20 i de efterfølgende.
I slutningen af 1870'erne blev Villa hurtigt områdets dominerende hold, og en særlig mindeværdig kamp var mod naboerne Small Heath, der blev besejret 22-0! I 1880/81 sæsonen vandt Villa 21 af 25 kampe og kunne til slut løfte sin første pokal som et synligt bevis på at have vundet Staffordshire Cup. Den nye klubs fremskridt blev yderligere synliggjort ved at nå kvartfinalerne i FA Cuppen i både 1883 og 1884. Snart skulle Villa også fejre en triumf i den berømte turnering - de vandt pokalen i april 1887 efter en 2-0 sejr over West Bromwich Albion på The Oval. Blot 13 år efter klubben blev stiftet, var Aston Villa en af de største i landet.
Året efter var Villa med i front i grundlæggelsen af The Football League, og det var klubbens direktør, William McGregor, som kaldte landets førende klubber sammen til møde den 2. marts. De tolv grundlæggere af den nye turnering blev først valgt ved et senere møde, og Villa var naturligvis med i det historiske dusin.
Den 8. september 1888 fik Aston Villa sin debut i den nye liga i en 1-1 kamp mod Wolverhampton, hvor Tom Green scorede klubbens første ligamål. Villa sluttede på 2. pladsen efter Preston i den nye ligas åbningssæson, mens det første mesterskab kom i 1893/94 sæsonen, hvor John Devey med sine 20 mål fik pokalen til Aston Villa. "Perry Barr Pets", som var klubbens kælenavn, scorede i alt 84 mål i de 30 kampe på vej mod titlen. Devey var på pletten igen et år efter, da han sikrede Villa klubbens anden sejr i FA Cuppen - igen efter en sejr over West Bromwich Albion. 1-0 sejren var en kærkommen trøst efter 0-3 nederlaget til samme klub i samme finale tre år tidligere. Senere skete der det, at den pokal, Villa vandt ved finalen i 1895, blev stjålet, da den skulle udstilles i Birmingham. På trods af der dengang blev udlovet en dusør på £10, er pokalen aldrig blevet fundet igen.
Villa blev mestre igen for anden gang på tre år i 1896, og året efter fik klubben endnu større succes ved at vinde The Double - både mesterskab og FA Cup. Villa sluttede med hele 11 points forspring til Sheffield United og vandt så 3-2 over Everton i en spændende FA Cup-finale. Den succesfulde sæson sluttede med at flytte hjemmebane til Aston Lower Ground (der senere skiftede navn til Villa Park), hvor 15.000 tilskuere mødte frem til klubbens første kamp på den nye hjemmebane, hvor Blackburn blev besejret 3-0. To år senere var en dramatisk sæson næsten færdig, før Villa i sidste runde besejrede rivalerne fra Liverpool med hele 5-0, og klubben kunne igen løfte mesterskabspokalen.