Terminato il ciclo Ranieri, sulla panchina viola arriva Alberto Malesani. Vengono ceduti Amoruso, Baiano, Carnasciali e Massimo Orlando, mentre Batistuta fa i capricci. Il bomber argentino vorrebbe cambiare aria ma rimane il trascinatore della squadra. Il campionato infatti inizia con la sua fantastica tripletta a Udine, nel triste giorno della morte di Lady Diana. La “ciliegina” di mercato arriva a gennaio dal Brasile e si chiama Edmundo. Il gradimento dei tifosi per il tecnico e la qualificazione alla Coppa UEFA non bastano a Malesani per essere riconfermato, a causa del rapporto conflittuale con Vittorio Cecchi Gori.
La campagna acquisti potenzia la rosa in maniera importante: Repka e Torricelli per la difesa, Amor e Heinrich per il centrocampo e l’inserimento definitivo di Edmundo per un attacco da sogno insieme a Batistuta e Oliveira, con Rui Costa trequartista. A dirigere la Fiorentina 1998-99 c’è Giovanni Trapattoni, uno dei migliori allenatori del momento, che conduce la squadra in vetta fino a febbraio, quando Batistuta si infortuna e Edmundo preferisce il carnevale brasiliano alle fatiche del campionato. Alla fine la Fiorentina arriverà terza, guadagnando il diritto di giocare i preliminari di Champions League. L’avventura in Coppa UEFA termina a causa della responsabilità oggettiva della società per la bomba carta di Salerno, ma la delusione più cocente arriva in Coppa Italia con la sconfitta nella doppia finale contro il Parma allenato dall’ex Malesani, che alzerà il trofeo proprio davanti al pubblico di Firenze.
Vittorio Cecchi Gori non ci sta e per la stagione 1999-00 rilancia: in difesa arrivano Adani e Pierini, a centrocampo Di Livio, Rossitto e l’australiano Okon, mentre in attacco Edmundo e Oliveira vengono rimpiazzati da Chiesa, Mijatović e dal vecchio Balbo. In campionato le cose non vanno per il verso giusto. Nei quarti di finale di Coppa Italia contro il Venezia, un rigore fallito da Chiesa all’ultimo minuto di recupero qualifica i lagunari a spese dei viola, i quali però onorano fino in fondo la Champions League. Tornata dopo trent’anni nella massima competizione continentale, la Fiorentina supera i preliminari battendo i polacchi del Widzew Łódź e supera anche la prima fase a gironi grazie alla epica vittoria di Wembley contro l’Arsenal. I viola si arrendono solo nella seconda fase, nonostante i sette punti ottenuti nelle prime tre gare del girone. Il campionato regala un piazzamento UEFA e soprattutto il record di gol in maglia viola in serie A di Batistuta. Dopo nove anni Batigol saluta Firenze con la tripletta al Venezia nell’ultima gara di campionato, raggiungendo quota 152 marcature. Anche Trapattoni chiude la propria esperienza in viola.
Per la panchina della Fiorentina 2000-01, la scelta della società cade sul turco Fatih Terim, fresco vincitore della Coppa UEFA con il Galatasaray, il cui gioco spregiudicato piace ai tifosi. Arrivano Amaral, Lassissi e Vanoli, mentre in attacco si cerca di rimpiazzare Batistuta con il brasiliano Leandro ed il portoghese Nuno Gomes. L’immediata eliminazione dalla Coppa UEFA per mano degli svizzeri del Tirol Innsbruck viene in parte compensata da alcune spettacolari prestazioni in campionato (soprattutto contro Inter e Milan) e dalla qualificazione per la finale di Coppa Italia. Ma gli screzi con Vittorio Cecchi Gori portano alle dimissioni dell’allenatore, seguito a ruota dal direttore generale Antognoni. In panchina Luciano Chiarugi, mister per una sola partita, precede l’arrivo di Roberto Mancini che ottiene una posizione tranquilla in classifica e soprattutto completa l’opera di Terim vincendo la sesta Coppa Italia della storia viola. Davanti al pubblico di casa, la Fiorentina pareggia contro il Parma grazie ad un bellissimo gol di Nuno Gomes e si aggiudica il trofeo in virtù della vittoria ottenuta nella gara di andata.
Le difficoltà economiche della società portano alle cessioni di Rui Costa al Milan e di Francesco Toldo all’Inter. Il confermato tecnico Roberto Mancini professa ottimismo, ma la stagione 2001-02 si trasforma in un calvario sportivo. Il grave infortunio di Chiesa precede di poco l’eliminazione dalla Coppa Italia e dalla Coppa UEFA. In campionato, nonostante l’arrivo in prestito dall’Inter del giovane talento Adriano, la squadra finisce in un vortice senza fine, con partite senza grinta e risultati disastrosi. La guida tecnica passa da Mancini a Chiarugi, a Bianchi e ancora a Chiarugi, il quale ha l’ingrato compito di accompagnare la squadra verso l’inevitabile retrocessione in serie B.