I juni 2003 kom den tidligere Leeds-manager David O'Leary til Aston Villa i endnu et kapitel af klubbens historie. O'Leary startede langsomt og fik kun to nye spillere til klubben i løbet af sommeren - Gavin McCann og Thomas Sørensen, begge fra Sunderland, og Villa var virkelig i problemer omkring juletid.
Nobby Solano kom til fra Newcastle, da transfervinduet åbnede i januar, og hans tilgang kom samtidig med, at alt ændrede sig for klubben. Villa's form i den anden halvdel af sæsonen blev kun overgået af mestrene fra Arsenal - og klubben sluttede på en sjetteplads, hvad der desværre lige nøjagtig ikke rakte til en plads i Europa (men med ét point mere havde klubben klaret en femteplads og Europa!).
Før sin anden sæson i klubben fik O'Leary ikke mange penge til at forstærke truppen, men det lykkedes ham at hente Martin Laursen i AC Milan, ligesom Carlton Cole og franskmanden Mathieu Berson kom til klubben. Sæsonen var mest kendetegnet ved talrige skader, hvad der i sidste ende betød, at klubben ikke kunne være med i opløbet om pladserne til Europa - og holdet sluttede som nummer ti. Angriberne scorede ikke ret mange mål, og i stedet var det midtbanespillerne - især Solano, Hendrie og Barry, der måtte træde til. Et lyspunkt i løbet af sæsonen var unge Steven Davis, der fik etableret sig på holdet med hele 29 kampe i sin debutsæson.
Efter en 6. plads i sin første sæson og en 10. plads i den næste gik det helt galt for O'Leary i 2005/06 sæsonen, der var hans tredje i spidsen for Aston Villa. På trods af han brugte mere end £13 mio. på forstærkninger som Milan Baros, Wilfred Bouma og Keven Phillips, ligesom James Milner blev lejet i Newcastle, endte holdet på en meget skuffende 16. plads, ligesom man meget ydmygende blev slået ud af Liga Cuppen af Doncatser fra den tredjebedste række, der uden problemer vandt 3-0 over et Villa-hold i noget nær stærkeste opstilling. O'Leary's tid i Aston Villa endte meget dramatisk i sommeren 2006. En lokal avis bragte et brev, hvor en gruppe anonyme spillere kritiserede klubbens ledelse for manglende ambitioner og for at holde for meget på pengene. Først afviste klubben det hele, men sagen udviklede sig, og det kom frem, O'Leary muligvis havde opfordret spillerne til at skrive brevet, fordi han selv var utilfreds med Doug Ellis og den øvrige ledelse. Det hele endte med, klubben og O'Leary "skiltes i enighed", som man skrev i pressemeddelelsen.
I første omgang tog O'Leary's assistent, Roy Aitken, over og styrede holdet gennem de første træningskampe forud for den kommende sæson. Men den 4. august - blot 15 dage før sæsonstart - kunne Doug Ellis ved en pressekonference fortælle, at man havde ansat Martin O'Neill som ny manager. Samtidig kørte der i pressen flere historier om, at Ellis selv var på vej ud, efter flere potentielle købere havde meldt sig til at overtage klubben. Det endte med at blive amerikaneren Randy Lerner, som opfyldte det ønske, de fleste fans havde haft i mange år - at få Doug Ellis væk fra Aston Villa. Og tirsdag den 19. september kunne klubben udsende pressemeddelelsen om, at Lerner nu ejede 90% af klubbens aktier og derfor tvangsindløste den resterende del og satte sig selv i sædet som ny bestyrelsesformand.
Den nye manager og klubejer kom godt fra start, og helt frem til december måned lå holdet omkring 4.-7. pladsen. På trods af at forstærkninger i form af John Carew, Ashley Young og Shaun Maloney blev hentet til klubben i januar, lykkedes det ikke at holde fast i toppen, og holdet sluttede sæsonen på en 11. plads. Optimismen var dog for alvor vendt tilbage til Villa Park, og holdet sluttede da også sæsonen af med ni kampe i træk uden nederlag, ligesom Martin O'Neill i løbet af foråret blev kåret til Månedens Manager i Premier League.
I sommerpausen fortsatte O'Neill arbejdet med dels at skabe sin egen trup og dels at skabe en trup, der var stærk nok til at kunne spille med om kvalifikation til Europa Cuppen. Han skilte sig bl.a. af med publikumsfavoritten Juan Pablo Angel og Steven Davis, som var et produkt af klubbens egen ungdomsafdeling. Til gengæld hentede han forstærkninger i form af Nigel Reo-Coker, Curtis Davies og den engelske landsholdsmålmand, Scott Carson, der fortrængte Thomas Sørensen til en tjans som reserve.
Sidste sæsons fremgang fortsatte, og et højdepunkt kom i fjerde spillerunde, da Chelsea blev besejret 2-0 på Villa Park. Sæsonen bød på masser af mål - i løbet af tre kampe i træk havde Villa en målscore på 15-1 (bl.a. en 5-1 ydmygelse af lokalrivalerne fra Birmingham City). Da sæsonen sluttede, var Villa på sjettepladsen, og holdet var det tredjemest scorende i ligaen, mens man i Ashley Young havde den spiller, der gennem hele sæsonen havde næstflest målgivende afleveringer kun overgået af Cesc Fàbregas fra Arsenal. Sjettepladsen betød, at Villa kvalificerede sig til UEFA Intertoto Cuppen og for første gang siden august 2002 igen skulle spille europæisk fodbold.
Martin O'Neill's karriere i Aston Villa varede fire år, og det blev fire år med nærmest konstant fremgang. Den sjetteplads, han hentede i sin anden sæson i klubben, blev gentaget både i 2008/09 og 2009/10, og begge år var Villa i lang tid med i kampen om den eftertragtede 4. plads, der giver kvalifikation til Champions League. Selvom Aston Villa igen efter mange års pause kvalificerede sig til europæisk fodbold flere sæsoner i træk, blev det aldrig den store succes. I 2008/09 gik holdet videre fra gruppespillet i UEFA Cuppen, hvorefter et meget ungt og reservespækket hold blev slået ud af CSKA Moskva, og året efter røg Villa ud allerede i Play Off-kampene efter nederlag til Rapid Wien. Til gengæld var der masser af succes i de hjemlige pokalturneringer, hvor Villa i foråret 2010 optrådte to gange på Wembley - først i finalen i Liga Cuppen og kort tid efter i semifinalen i FA Cuppen. Desværre med nederlag begge gange.
Samtidig med fremgangen i ligaen og pokalturneringerne samt de gentagne kvalifikationer til europæisk fodbold fik O'Neill også skabt et hold med mange engelske spillere, hvilket igen gjorde, at Villa blev repræsenteret på det engelske landshold. Efter ikke at have været udtaget i nogle år fik Gareth Barry comeback, og der blev landsholdsdebut til James Milner, Gabriel Agbonlahor og Ashley Young, ligesom også Stephen Warnock kom med omkring landsholdet igen, uden han dog opnåede spilletid. Der kan siges meget om den måde, Martin O'Neill behandlede sine spillere på - især dem, som ikke lige var inde i varmen - og hans evne, eller mangel på samme, til at rotere i startopstillingen og give reserverne spilletid, samt de enorme summer han brugte på spillere, som kun fik plads på bænken. Men fakta er, at han flyttede Aston Villa fra at være et midterhold, som endda ind imellem kæmpede imod nedrykning, til at være et hold, der i over 2½ sæson i træk konstant lå i top 7, nåede langt i pokalturneringerne, flere sæsoner i træk spillede med i Europa samt igen var godt repræsenteret på det engelske landshold.
De fire år med Martin O'Neill sluttede meget brat, bare fem dage før 2010/11 sæsonen begyndte. Gennem sommerpausen havde der været flere rygter om, at kemien mellem klubejer Lerner og manager O'Neill ikke længere var så god som tidligere, og samtidig var O'Neill frustreret over, at han i sommeren 2009 havde mistet Gareth Barry til Manchester City, og nu et år efter stod til at miste James Milner til samme klub. Randy Lerner ønskede udgifterne til spillerlønninger nedbragt, mens O'Neill dels ønskede at holde på sine profiler og dels ønskede at forstærke holdet i kampen om 4. pladsen og Champions League. Derfor virkede bruddet uundgåeligt, men det kom som en overraskelse for de fleste, at det skete så tæt på sæsonstart.
Efter afskeden med Martin O'Neill fulgte en række sæsoner uden stabilitet, med konstante udskiftninger på managerposten og med en nærmest uundgåelig nedrykning til Championship liggende seks år ude i fremtiden. I første omgang overtog reserveholdets træner Kevin MacDonald managerposten, og der gik en hel måned af sæsonen, før franskmanden Gérard Houllier blev ansat som ny manager og yderligere to uger, før han kunne tiltræde i klubben, da han først skulle afslutte sin ansættelse i det franske fodboldforbund. I april måned blev Houllier pludselig sygemeldt og vendte aldrig tilbage til Aston Villa, hvor hans assistent Gary McAllister i stedet styrede holdet de sidste runder af sæsonen. Inden sin sygemelding og efterfølgende afsked med klubben havde Houllier dog slået klubbens transferrekord, da han i januar-vinduet hentede Darren Bent i Sunderland for £18 mio., en pris der kunne stige til £24 afhængig af præstationerne. Holdet havde ikke nogen videre god sæson under de skiftende managere, men sluttede efter en flot slutspurt med blot ét nederlag i de sidste otte runder dog på en ganske acceptabel 9. plads.
En ny manager skulle ansættes, og her skete noget, man nok sjældent ser, nemlig at klubbens fans mødte op for at protestere, da manageren skulle præsenteres. Aston Villa chokerede nemlig alt og alle, da man frikøbte Alex McLeish hos ærkerivalerne Birmingham City! Den dårlige stemning blandt fansene blev bestemt ikke bedre, da man igen, igen solgte ud af profilerne. Denne sommer blev det Ashley Young, der røg til Manchester United, og Stewart Downing til Liverpool, og herefter fulgte en sæson, hvor man brød en masse negative rekorder. Blandt andet var de blot syv sejre klubbens laveste antal på en sæson, og de sølle 19 point hentet hjemme på Villa Park var det dårligste nogensinde i klubbens mangeårige historie. Aston Villa sluttede på en meget skuffende 16. plads blot to point over nedrykningsstregen, og for at gøre sæsonen endnu værre, måtte anfører Stiliyan Petrov indstille karrieren efter i foråret at have fået konstateret leukæmi.
Den dårlige sæson blev afsluttet med endnu en udskiftning på managerposten efter en fyring af McLeish, og hans afløser blev Paul Lambert, som man hentede i Norwich, hvor han havde imponeret gennem tre sæsoner. Lambert fik bl.a. som opgave at få reduceret klubbens udgifter til spillerlønninger, hvor de konstante udskiftninger på managerposten betød, at der gik adskillige spillere rundt på dyre kontrakter, fordi Lamberts forgængere havde set en idé med dem, men nu kunne de ikke længere bruges. Lambert hentede derfor primært sine forstærkninger i de lavere rækker eller i mindre udenlandske klubber, bl.a. fandt han Christian Benteke i belgiske Racing Genk. Benteke fik en forrygende start i engelsk fodbold og blev med 19 ligamål Aston Villas topscorer og nummer fire på Premier Leagues topscorerliste. Knap så godt gik det for Lambert, der ikke fik en god første sæson i Aston Villa, og tæt på sæsonens afslutning lå holdet under nedrykningsstregen men sluttede dog på en 15. plads, fem point over stregen. Så havde klubbens ungdomshold mere succes i den nystartede NextGen Series-turnering, hvor man blev mestre i turneringens anden sæson. Paul Lambert fik lov at fortsætte sit arbejde i klubben og hentede i sommeren 2013 bl.a. to danskere til klubben; Jores Okore og Nicklas Helenius. Sæsonen igennem lå holdet omkring 10.-12. pladsen, men i april blev topscorer Christian Benteke desværre alvorligt skadet til træning og gik både glip af sommerens VM og også de sidste kampe i Premier League. I sæsonens sidste ni kampe hentede holdet blot én sejr og sluttede således for anden sæson i træk på 15. pladsen.
Da sæsonen var slut, meddelte klubejer Randy Lerner, at han efter otte sæsoner som ejer af Aston Villa ville sælge klubben, og da der ikke umiddelbart stod nogen klar til at overtage hans post, kunne man frygte, det nu var slut med investeringer i nye spillere. Der var delte meninger, om holdet havde rykket sig under de to sæsoner med Paul Lambert, men han fortsatte som manager, da 2014/15-sæsonen gik i gang. I sommerpausen havde man bl.a. taget afsked med Marc Albrighton, der havde spillet i Aston Villa hele sin ungdomskarriere, og som to år senere skulle blive engelsk mester med Leicester. Det blev heller ikke denne sæson, hvor Aston Villa kom tilbage i toppen af ligaen, og i februar 2015 efter ti kampe i træk uden sejr og nederlag i de seneste fem blev Lambert fyret, og posten som manager blev overtaget af Tim Sherwood. Han reddede holdet fra nedrykning, hvilket var hans vigtigste opgave - det endte med en 17. plads - men samtidig hentede han lidt succes i FA Cuppen. På et fyldt Wembley Stadium vandt Aston Villa 2-1 over Liverpool i en forrygende semifinale men faldt så desværre helt fra hinanden i finalen, hvor man med 0-4 blev kørt fuldstændig over af Arsenal.
Sæsonen 2015/16 skulle gå over i historien som den værste for Aston Villa i nyere tid. Tim Sherwood var manager, da sæsonen begyndte, men allerede i oktober blev han fyret, efter ti kampe kun havde udløst fire point. Franskmanden Rémi Garde tog over, og han holdt til marts året efter med blot to sejre i 20 kampe, og så blev Eric Black indsat som midlertidig manager med en umulig opgave - at redde Aston Villa fra den uundgåelige nedrykning. Det blev til sølle ét point i de sidste syv kampe, og allerede efter hans tredje kamp som manager var nedrykningen en matematisk kendsgerning, og for første gang siden 1987 var Aston Villa ikke længere en del af den bedste engelske fodboldrække. Men sådan måtte det være, når man i løbet af sæsonen bl.a. havde sat den negative klubrekord med hele 19 kampe i træk uden en sejr. Nedrykningen betød bl.a., at klubben gik glip af massive tv-indtægter, hvilket førte til massefyringer blandt klubbens mange ansatte uden for fodboldbanen. Efter at have haft klubben til salg i to år, lykkedes det efter nedrykningen for amerikanske Randy Lerner at finde en køber, da kinesiske Tony Xia købte Aston Villa, og sammen med den nye italienske manager Roberto Di Matteo ventede der nu et kæmpe oprydnings- og genopbygningsarbejde.