Vålerenga spilte på Bislett gjennom storhetstidene på 60- og 80- tallet. Laget gjorde det så bra at Bislett på folkemunn fikk navnet "Lekegrinda".  I 1962 satte klubben en publikumsrekord som ikke ville bli brutt før i 2004.
Bislett var Vålerengas hjem, men Oslo kommune som er eieren av stadion gjorde ikke sine plikter som en god husvert skal gjøre. Mangelfullt vedlikehold gjorde at stadion forfalt. Etter hvert ble forholdene så dårlige at klubben ble nødt til å finne andre arenaer å spille på.
Selv om forholdene på Bislett var elendige vendte Vålerenga tilbake i siste halvdel av 90- årene etter å ha spilt sine kamper på blant annet Ullevål.

På 90- tallet ble det klart at Vålerenga hadde store planer om å bygge en egen arena/fotballhall ved siden av Valle Hovin. Alle planer og finansiering var i orden, samtidig som flere lokale politikere var positive. Til tross for dette fikk VIF et nei fra Plan og Bygg rett før julen i 1997. Klubben nektet å gi slipp på planene og oppfordret samtidig de politikerne som i utgangspunktet var positive til planene om igjen å jobbe for saken.

I 1999 ble det klart at VIF måtte returnere til Ullevaal Stadion. Dette skapte store negative reaksjoner. Bislett var i alt for dårlig stand, samtidig som debatten om en ny Bislett raste i mediene. Vålerenga var den største brukeren av stadion, men klubbens ønsker rundt "nye Bislett" ble likevel ikke hørt. Med en "tvungen" deportering til Ullevål og intet gehør hos kommunen, begynte planer om en egen stadion å vokse fram. Flere alternative byggeplasser ble nevnt, som for eks. Bjørvika, og Kværnerdalen/Lodalen som bare ligger et steinkast fra Vålerenga Kirke.
Etter en del snakk i media rundt nyklekkede stadionplaner, ble oppmerksomheten rundt en ny arena gradvis borte. Vålerenga flyttet tilbake til Ullevål og praten rundt et nytt anlegg stilnet.

Rett etter årtusenskifte startet en ny og spennende periode for VIF. Fotballhallen på Valle, hvor oppføringen hadde blitt stanset i 1997, ble likevel en realitet. Vallhall som arenaen heter, ble klar til bruk på slutten av år 2000. VIF hadde nå fått en hall som gav dem noen av de beste treningsforholdene i landet. År 2000 var et godt år for Vålerenga med tanke på Vallhall, men sportslig var året en katastrofe. VIF rykket ned fra Tippeligaen og måtte finne seg i å spille i 1. divisjon i 2001. Til tross for suksessen med Vallhall, ble det derfor ikke noe mer snakk om byggingen av en egen stadion.

2001 skulle vise seg å bli et bra år for Vålerenga. Tom Nordli ble erstattet av Kjetil Rekdal som hovedtrener, og Rekdal svarte med å bringe laget rett tilbake til Tippeligaen. 11 Oktober 2001 våknet VIF-supporterne til en stor nyhet. I all stillhet hadde Vålerenga Fotball ASA, Vålerenga Hockey AS og Vålerenga Basket planlagt en 100% privatfinansiert idretts- og næringspark i Jordal-dumpa. Planene gikk ut på at det skulle bygges en ny fotball-stadion, under navnet "Vålerenga Park", næringslokaler og boliger. Anlegget var planlagt ferdigstilt rundt årsskifte 2006 – 2007.
Konsortiet som planla "Vålerenga Park" besto av Vålerenga Fotball ASA, Vålerenga Hockey AS, Vålerenga Basket, Oslo Kommune og tyngre aktører som Entra Eiendom og AF-gruppen. Håpet var at Oslo kommune skulle frigjøre tomten til Vålerenga og samtidig omregulere området. 
Drømmen om en egen stadion så for første gang ut til å bli virkelighet. Optimismen levde, og selskapet "Vålerenga Park AS" ble stiftet. Vålerenga Fotball ASA og Vålerenga Hockey gikk hver inn med kr 200.000,- i egenkapital.

2002 ble nok et godt år sportslig for Vålerenga. "Enga" ble Norgesmestere og holdt seg i Tippeligaen med god margin. Planene om en ny stadion ble videreutviklet og alt gikk tilsynelatende på "skinner". 

Året 2003 skulle vise seg å bli langt mer spennende enn det noen kunne forutse. Flere av de mest profilerte spillerne forlot klubben, deriblant, Pa Modo Kah, Tobis Grahn og Stian Ohr. Resultatet var at klubben gjorde det elendig i serien og Vålerenga måtte til slutt ut i kvalifiserings-kamp mot Sandefjord. Klubbens framtid så veldig mørk ut.
Årets siste kamp ble spilt i Vallhall. Det var vinn eller forsvinn for Vålerenga. Økonomien til Vålerenga Fotball ASA var elendig, og et nedrykk ville bare gjøre denne situasjonen verre. På grunn av den dårlige økonomien truet NFF med å ikke innvilge VIF lisens, for spill i toppdivisjonene. Om ikke økonomien på kort sikt forbedret seg drastisk, ville det ført til at klubben måtte ha spilt i 2. divisjon.
Vålerenga vant kampen mot Sandefjord, og nedrykk ble unngått rent sportslig. Rett etter seieren i Vallhall ble det annonsert at "Vålerengas store venn" Skipsreder Fredriksen hadde slettet hele Vålerengas gjeld. Vålerenga Fotball ASA ble lagt ned/slått konkurs og alle rettigheter ble overført til klubben Vålerenga Fotball. Norges Fotball Forbund innvilget Vålerenga profflisensen og VIF hadde fått en ny start "med blanke ark og fargestifter til".
Selv om denne omveltningen var utelukkende positiv, førte det til at Vålerenga fotball ASA som eide 50% av aksjene i stadion-prosjektet "Vålerenga Park AS"  ble lagt ned. Igjen ble planer om en ny stadion lagt på is.

Opprydning og ny giv preget Vålerenga på slutten av 2003 og begynnelsen av 2004. "Ingen" snakket lenger om en ny stadion. Tanker rundt nesten-nedrykk og økonomiske problemer ble feid bort da VIF i 2004 gjorde jobben sin både sportslig og økonomisk. Året ble for klubben et rekordår på alle måter. Sølv i serien á poeng med Rosenborg som vant, kvalifisering til nye "Royal League" og til "Champions League", samt at det ble satt to nye publikumsrekorder. Klubben tjente penger som aldri før og en økonomisk rekord ble satt da Vålerenga og Hafslund ble enige om den største sponsoravtalen klubben hadde hatt.
Dessverre var det lite snakk om "Vålerenga Park" prosjektet som da virket et lysår unna realisering. Helt på tampen av året 2004 ble det annonsert at Entra Eiendom gikk inn i Vålerenga Fotball som en ny hovedsamarbeidspartner. Avtalen skal gjelde fram til 2010. Fra VIF kom så innrømmelsen om at en fremtidig utvikling av en egen stadion ligger inklusivt i avtalen med Entra.

2004 hadde vært et fantastisk år på alle måter, men 2005 skulle vise seg å bli enda bedre. For Vålerenga supportere som gjennom årenes løp har vært vitne til den ene skuffelsen etter den andre var sølv fra 2004 en kjempebragd. At 2005 skulle bringe klubben enda lengre opp på rangstigen i Norsk fotball var nesten for godt til å være sant. VIF tok gull i serien samtidig som fjorårets publikumsrekord mot Stabæk ble grundig slått. Enga var tilbake helt på toppen av Norsk fotball etter et avbrekk på hele 21 år. Som tidligere i Vålerengas moderne historie har sportslig suksess og planer om en ny stadion fulgt hverandre tett. 2004 hadde hatt veldig lite å by på med tanke på utviklingen av et nytt fotballanlegg, men med kontinuerlig sportslig suksess ble nye planer presentert. I April 2005 ble det fra VIF meddelt at de sammen med Entra vurderte tre alternativer for plasseringen av en eventuelt ny stadion. De tre alternativene var Jordal, Valle og Bjørvika. En måned etter at Vålerenga kom med den første uttalelsen kunne flere av landets aviser meddele at VIF hadde bestemt seg for Bjørvika. Til å begynne med ble dette avkreftet av Engas direktør Kjetil Siem, men etter noen spennende uker ble det endelig bekreftet at Bjørvika faktisk var klubbens førstevalg. At VIF ønsket å legge en ny fotballstadion til Norges mest attraktive område skapte naturligvis mye debatt. Kort tid etter at Bjørvikaplanene hadde blitt presentert kom det uttalelsen fra flere politikeren og felles for nesten alle var at de var sterkt negative til Vålerengas planer. Bjørvika var regulert til boligformål og byens styrende organer så ingen grunn til å endre på det. Til tross for politisk motvilje fortsatte Vålerenga og Entra arbeidet med å utvikle planene for en stadion i Bjørvika og en lett muntlig feid mellom kommunen og Vålerenga blusset opp. Oslo kommune beskyldte Vålerenga for å ikke respektere vedtatte planer, mens Enga kritiserte kommunen for å ikke støtte toppfotballen slik andre kommuner gjorde. Som en reaksjon på VIF sine stadionplaner i Bjørvika lanserte Oslo Venstre Ensjø som et nytt alternativ for plassering av klubbens nye hjemmebane. byutviklingskomiteens leder Ola Elvestuen kunne gjennom Dagsavisen fortelle at både byens politikere og grunneierne på Ensjø så positivt på å legge en ny VIF arena til området. Et av argumentene til Ola Elvestuen var at Ensjø var i kjærneområdet til Vålerenga og at kostnadene i forbindelse med å bygge en stadion ville være mye billigere på Ensjø sett i forhold til Bjørvika. Etter at Ensjø hadde blitt presentert som et nytt alternativ reagerte Vålerenga med å meddele at planene var interessante, men utover det kom det ingen flere signaler fra klubben. Da planene om en ny arena i Bjørvika først ble kjent hersket det noe usikkerhet rundt hvor konkrete disse planene faktisk var, men den usikkerheten skulle fort bli fjernet. I September 2005 presenterte Entra Eiendom planene for "Fjordbyen" i Bjørvika. Dette var planer som omhandlet en komplett utnyttelse av området hvor fotballstadion "Enga Amfi" var plassert på Sørenga i Bjørvika.