Gais slutade säsongen 1999 på andra plats i division I södra och lyckades genom att besegra Kalmar FF nå Allsvenskan för första gången sedan 1992. Strategin för Allsvenskan var en lågbudgetsatsning där man gjorde sig av med de svagaste spelarna i truppen, men inte ersatte dessa med spelare med allsvensk rutin utan främst plockade in spelare från lägre divisioner. Bland de spelare som kom in märks Ivan Ottordahl (Örgryte IS, son till dåvarande Gaistränaren Lennart Ottordahl), Lasse Johansson (Kalmar FF), Niclas Fredriksson (IF Sylvia, son till Gaislegendaren Eine Fredriksson) och Simon Sjöfors (Mjällby AIF).
Under vårsäsongen gick Gais mycket dåligt. Det i stora delar helt nykomponerade laget fick inte alls spelet att fungera, och Gais vann inte en enda match före EM-uppehållet. En av få ljuspunkter under våren var en sen kvittering av nye Simon Sjöfors i derbyt mot IFK Göteborg då Gais nådde oavgjort mot rivalen.
Efter EM-uppehållet gick det något bättre; Gais lyckades i början av juli äntligen ta sin första trepoängare genom 2–0 borta mot Trelleborgs FF, och lyckades under juli månad även besegra BK Häcken på bortaplan. När serien vände efter 13 omgångar låg Gais på 13:e och näst sista plats, och var tre poäng ifrån kvalstrecket. Under sommarens transferfönster knöt man till sig den rutinerade försvararen Magnus Sköldmark från Dundee United, vilket orsakade förvåning, då Gais problem inte alls hade varit i defensiven. Klubben var snarare i desperat behov av en målskytt.
Även under höstsäsongen hade Gais förtvivlat svårt att vinna matcher. Först i omgång 23 kom nästa vinst, men Gais hade efter denna fortfarande sex poäng upp till kvalstrecket. Det fanns dock ett litet hopp kvar om att hamna på kvalplats, då de tre återstående motståndarna också var lag på undre halvan. Gais styrelse gick då plötsligt in och sparkade tränare Ottordahl, som emellertid skulle fortsätta leda laget under de återstående tre omgångarna. Gais förlorade sin nästa match mot Hammarby IF med 2–4. I samma omgång fick BK Häcken oavgjort mot AIK, vilket innebar att Gais var avsågat i botten och inte kunde nå kvalspel. De två sista omgångarna blev därmed betydelselösa för klubben, som fick börja om i Superettan 2001.
