Turner blev erstattet af Billy McNeill, men klubben rykkede alligevel ned - otte point fra sikkerhedszonen. Tilbage i 2. division for første gang i 12 år begyndte Villa 1987/88 sæsonen med endnu en ny manager, Graham Taylor, som havde et godt rygte fra sin tid i Watford. Han startede med at lave en større ændring på holdet, og Kevin Gage, Steve Sims og Alan McInally kom ind på holdet, mens Gary Williams, Paul Elliot og Tony Dorigo blev solgt. Holdet havde problemer i de første uger under den nye manager og vandt kun en enkelt gang i deres første seks kampe. Vendepunktet kom med en udesejr over West Bromwich Albion, og herefter satte holdet for alvor kursen imod en tilbagevenden til den bedste række. Til sidst blev det dog meget tæt, da Villa lige klarede at få ét point imod Swindon, mens de nærmeste forfølgere fra Bradford og Middlesbrough tabte deres sidste kamp. Resultaterne betød, at Villa sikrede sig andenpladsen i divisionen og dermed oprykning.
Næste sæson handlede om at konsolidere sig i den bedste række, og i den efterfølgende sæson var Taylor så klar med flere ændringer. Han forstærkede holdet med to forsvarsspillere, Kent Nielsen og Paul McGrath. Med det par sammen med klassespillere som Gordon Cowans, Tony Daley og David Platt kunne holdet for alvor blande sig i topstriden. De forfulgte Liverpool på førstepladsen gennem hele sæsonen og endte til sidst som nummer to. Desuden opnåede man en kvartfinaleplads i FA Cuppen. Oveni en rigtig god sæson lykkedes det Platt at komme på det engelske landshold ved VM i 1990. Han blev kort efter efterfulgt af manager Taylor, som blev udnævnt til landstræner efter VM.
Så da 1990/91 sæsonen begyndte, var Villa igen på udkig efter en ny manager. Doug Ellis valgte et noget dristigt træk og udpegede den tjekkiske landstræner Jozef Venglos. Det gik imidlertid ikke, som man havde håbet - og i den efterfølgende sæson blev Venglos erstattet af Ron Atkinson. "Big Ron" kom ind på Villa Park med en klar målsætning om at skaffe hæder til klubben og startede med en hektisk transfer-aktivitet. Ti spillere forlod klubben, mens 11 spillere kom til i første omgang. Men det var også det, der skulle til, for langt om længe at få lidt succes til klubben. Hvad der også var vigtigt var, at han var manden bag makkerparret Dalian Atkinson og Dean Saunders. De to hjalp Villa til sejr i Liga Cup-finalen i 1994, hvor holdet vandt med 3-0 over favoritterne fra Manchester United. Så langt om længe kom der en pokal til klubben, men liga-formen var desværre ikke lige, hvad man havde forventet. Til sidst tabte Doug Ellis tålmodigheden med Atkinson, der blev fyret.
Formanden handlede derefter hurtigt og fik Brian Little til Villa Park. Little havde en fortid som en fremragende angriber for klubben i 70'erne. Den nye manager fik Alan Wright og Gary Charles til klubben for sammenlagt £1,8 millioner, mens Ian Taylor, der hele sit liv havde været Villa-fan, kom til klubben for at forstærke midtbanen. Holdet klarede at undgå nedrykning i den sæson, og det blev i stedet Crystal Palace, der måtte ned på allersidste spilledag. Flere spillere kom til klubben inklusiv Gareth Southgate, Ugo Ehiogu, Mark Draper og selvfølgelig Savo Milosevic. På første kampdag i 1995/96 sæsonen vandt holdet 3-1 over United, og det var ikke bare en enlig svale - holdet sluttede som nummer fire i rækken.
Oveni betød en udesejr over Arsenal i Liga Cuppen, at holdet endnu en gang var i finalen - og holdet udnyttede den kamp til at vise en af sine bedste optrædener på Wembley. Foran 77.065 tilskuere scorede Milosevic et af sine bedste mål midt i første halvleg. Taylor scorede derefter nummer to, og efter godt samarbejde med Wright snød Savo fuldstændig forsvaret og skubbede bolden videre til Yorke, der kunne afslutte arbejdet. Hvis finalen var højdepunktet i Savo's karriere, så bød den næste sæson på lavpunktet. I en kamp imod Blackburn, hvor fansene så holdet tabe 0-5, lagde de ikke ligefrem skjul på, hvad de mente om holdet og især Milosevic. Han havde spillet skidt, men intet kunne undskylde hans reaktion med at spytte i fansenes retning. Han blev sat på transferlisten ugen efter og endte med at forlade klubben ved sæsonafslutningen - men ikke før Brian Little havde sagt farvel.
Der var mange spekulationer om, hvem der skulle tage over, men Ellis handlede igen hurtigt og fik John Gregory til klubben. Den tidligere Wycombe Wanderers-boss gik straks ud på transfermarkedet og fik Paul Merson, Dion Dublin, Steve Watson, Colin Calderwood, Mark Delaney og Steve Stone til klubben. Det var med til at opveje tabet af Dwight Yorke, som Manchester United købte for klubrekorden på £12,6 millioner.
Efter at have afsluttet sin første sæson i klubben var Gregory sikker på, at hans hold nok skulle klare sig godt i 1999/2000 sæsonen. Han fik flere nye spillere til klubben i form af George Boateng og David James. I kampen om en plads i Europa blev det til en sjetteplads for klubben, men det var især klubbens præstationer i Cup-turneringerne, der imponerede fansene. Villa klarede sig rigtig godt og nåede semifinalen i Liga Cuppen, men det var FA Cuppen, der for alvor gjorde folk begejstrede. Benito Carbone var kommet til klubben efter jul for at erstatte Dion Dublin, der havde brækket nakken. Og italieneren scorede et fantastisk hattrick mod Leeds, så klubben klarede sig videre til femte runde. Efterfølgende sejre imod Everton og Bolton fik klubben videre hele vejen til Wembley. Desværre var det ikke ligefrem en dag, man gider huske på, da det blev til et 0-1 nederlag til Chelsea, hvor Roberto Di Matteo scorede det afgørende mål.
Sommerpausen bød på en større rokade med Steve Watson, Mark Draper, Alan Thompson og Stan Collymore på vej ud - mens David Ginola, Alpay Özalan og Luc Nilis kom til klubben. Nilis' karriere i klubben sluttede nærmest, før den begyndte, da han i en af sæsonens første kampe stødte ind i Ipswich's målmand Richard Wright og fik en skade, der betød, at han måtte afslutte karrieren. Gregory må have tænkt, at det ikke kunne blive værre, men det blev det, da Ugo Ehiogu forlangte at komme væk - og til sidst kom til Middlesbrough for £8 millioner. Selvom Juan Pablo Angel, Moustapha Hadji, Olof Mellberg og Peter Schmeichel kom til klubben, så fulgte anfører Southgate med Ehiogu til Middlesbrough for £6,5 millioner.
Resultaterne i 2001 var meget svingende, og holdet endte på en 8. plads. Gregory overraskede alt og alle i januar 2002, da han trak sig fra posten og i stedet gik til nedrykningstruede Derby County. Ikke underligt var der endog mange skriverier om det. To uger senere udnævnte Ellis så den mand, som han aldrig havde ønsket at miste som manager - og Graham Taylor blev boss. Taylor var kommet til klubben som fodbold-direktør efter at have trukket sig tilbage fra managerlivet efter at have været hos Watford. Han havde besluttet sig for, at dagene på træningsbanen var ovre - indtil formanden gav ham et tilbud, som han ikke kunne afslå.
Han største køb var Peter Crouch fra Portsmouth, mens Dion Dublin brugte resten af sæsonen som udlånt til Millwall. Villa endte i sidste ende på endnu en 8. plads. Den efterfølgende sæson gik ikke efter planen, og klubben endte som nummer 16 - mest fordi holdet ikke var i stand til at vinde på udebane, med en enkelt undtagelse i form af en 5-2 sejr over Middlesbrough. Resultatet blev, at Taylor trak sig, og klubben skulle igen ud at finde en ny manager.