La Fortis nasce nel giugno del 1999 con lo scopo di far rivivere il vecchio, glorioso, Trani, rotolato in basso e cancellato, due anni prima, dalla geografia del calcio: la società infatti, era stata esclusa dal campionato pugliese di Eccellenza, nel quale era retrocessa per la pesante situazine economica (in pratica era stata radiata). La Fortis nasce da una complessa serie di operazioni messe in atto da un gruppo di imprenditori (fra i quali anche alcuni ex giocatori del Trani) che hanno garantito due obiettivi: continuità col passato ed iscrizione ad un campionato meno anonimo (la Promozione Pugliese) della terza categoria dalla quale partono, in genere, tutte le società di nuova costituzione. Un terzo obiettivo era appena accennato: restituire al nuovo, vecchio, Trani un ruolo degno del suo blasone e dei suoi settant'anni di storia.

Così dopo l'Unione Sportiva Trani ( 1929-1932 ), l'Associazione Sportiva Trani ( 1932-1935 ), la Società Sportiva Trani ( 1938-1949 ), la Polisportiva Trani ( 1949-1997 ), ecco l'Associazione Sportiva Fortis Trani la cui nascita è scandita da cinque date. Il 15 giugno 1999 il gruppo di imprenditori su citato entra nel CdA della Libertas Barletta, società di Promozione il cui titolo sportivo è in vendita. Il 18 giugno, dopo aver liquidato i vecchi dirigenti, acquisito il capitale giocatori, viene formato un nuovo CdA che trasferisce la sede da Barletta a Trani. Il 22 giugno il CdA cambia la ragione sociale iscrivendo al campionato di Promozione l'Associazione Sportiva Fortis Trani. Il 27 agosto la nuova società, i dirigenti, i giocatori e lo staff tecnico vengono presentati al pubblico su un palco eretto in piazza della Repubblica. Il 30 agosto 1999 l'esordio in Coppa Italia: al Comunale di Trani il Bisceglie viene battuto 2-0. Al vecchio nucleo di giocatori della Libertas (Mennea, Camasso, Borracino, Paparella, Musti), l'allenatore-manager Nicola Di Leo (ex portiere di serie A e ora anche dirigente) aggiunge i nuovi acquisti: i portieri Cuccovillo e Carlucci, i difensori Chiricallo (un altro ex Polisportiva), Amoruso, Gusmai, Parente, i centrocampisti Carelli, Di Leo, Bagnara (altro ex), gli attaccanti Baldassarre, Maffione e Lamonaca, e poi D'Aloia, Telesca, Bovio (altro ex Polisportiva). La squadra si ritrova subito: infila una serie di risultati che la portano ai vertici della classifica battendosi alla pari con Castellana, San Paolo e Bitonto. Al termine del campionato precederà tutti conquistando così la promozione in Eccellenza dopo aver chiuso il torneo imbattuta. Capocannoniere è Michele Musti con 20 gol.

Nel campionato successivo (2000/2001) la squadra , dopo un buon avvio, si smarrisce finendo a centro classifica nonostante il cambio di allenatore (Chiricallo al posto di Di Leo ) e i rinforzi (Foggetti, Cesareo, Campanale, Fragasso, Tenzone, Pascazio e Di Bari).
Tali innesti si riveleranno comunque utili per il successivo balzo di categoria. Capocannoniere è ancora Michele Musti con 16 gol.
In Coppa Italia la compagine tranese arriverà alla semifinale regionale perdendo ai rigori con il Castellaneta.

Nel 2001/2002 ecco la seconda promozione: questa volta in serie D. Un nuovo allenatore (Sergio Notariale), acquisti indovinati (Tenzone, De Santis, Cacciapaglia, Vurchio, Martiradonna, De Tullio, Luciani ed il bomber Pica) e la riconferma dei migliori uomini permettono al pubblico sportivo tranese di godersi un campionato da leader. In zona gol esplodono Tenzone (23 reti), Pica (20) e Musti (8). La squadra è una macchina da gol: ne segna in totale 78 anche se poi vince il campionato con un solo punto di vantaggio sul Noicattaro. Decisiva si rivelerà la penultima giornata: i tranesi espugnano Lucera (2-1) in uno stadio gremito di tifosi biancazzurri in festa.

Nel 2002/03 viene confermato Notariale, arrivano il portiere Castelletti, i difensori Bartoli, Chirico, Tafuni, i centrocampisti Bitetto, Quaresimale, Piccirilli, gli attaccanti Bosco e Stramaglia. A gennaio poi arriveranno dal Martina il portiere Petruzzelli ed il centrocampista Branà. Il primo campionato di serie D della Fortis trascorre tra alti e bassi. Dopo un ottimo girone di andata la squadra sembra smarrirsi e si ritrova di colpa dalla zona play off ai margini della zona play out. Ma i 27 punti del girone di andata costituiscono una buona rendita che alla fine garantisce l'ottavo posto finale.
A fine campionato però si profilano una serie di difficoltà societarie che influiscono sui programmi per la stagione 2003/2004. La maggioranza dei dirigenti annuncia l'intenzione di lasciare, si parla di vendita del titolo sportivo. La mediazione del nuovo sindaco, Giuseppe Tarantini (un trascorso da ultras e da medico sociale della scomparsa Polisportiva) contribuisce a sbloccare la situazione.

La società riparte con ambizioni e budget provvisoriamente ridimensionati. Nuovo presidente dal settembre 2003 è l'imprenditore calzaturiero Ilario Monterisi: è il 44esimo della serie, primo ex calciatore tranese (28 partite e 5 gol nel 1973/74) ad assumere questa carica. Francesco Simone, presidente nei 4 anni precedenti, assume l'incarico di direttore generale. Al posto di Notariale in panchina si accomoda il coratino Michele Lotito. La crisi societaria ha spinto tutti i giocatori dell'anno precedente ad andar via. Ad inizio stagione restano solo in cinque: Musti, Bagnara, De Santis e Cacciapaglia, oltre ai giovani Amantino e Fiorella. Torna De Tullio (protagonista del campionato vinto in Eccellenza). Per il resto è una squadra completamente nuova: Torre, Gallo, Tridente (già a Trani in C2: giocò solo 3 partite), Santoro, Angelastro, Loporchio, Minno, Carlucci, Bucci, Gravina, Marino e la gustosa novità dell'argentino, il terzo della storia del Trani: si chiama Ariel Gaston Ojeda, 25 anni, professione attaccante, da 5 in Italia dove ha sempre giocato con la maglia di squadre siciliane.

La stagione si rivela deludente. Il Trani retrocede in Eccellenza e perde anche un altro tassello societario. Va via Ilario Monterisi. Sulk ponte di comando resta solo Francesco Simone che, nonostante le ristrettezze economiche, non getta la spugna anche se i risultati non lo premiano. La Fortis conosce una parabola discendente che, nel giro di pochi anni, la riporta lì dove aveva cominciato, ovvero dal campionato di Promozione.

Tutto da rifare.