La società nasce nell'estate del 2000, dalle ceneri della Cestistica Barcellona, passata in pochi anni dalla serie D alla A2. La rapida crescita causa il disimpegno dell'allora presidente Edo Capizzi, che non riuscì più a mantenere una squadra nel secondo campionato nazionale e fu costretto a cederne la proprietà. A portare la pallacanestro di vertice a Messina sono due imprenditori cittadini, Nino Piccolo e Pippo Caruso. Mesi di duro impegno, in particolar modo di tipo burocratico, e poi l'approdo del titolo in città con il cambio di denominazione in Pallacanestro Messina. La nuova società conferma il coach di sempre, Giovanni Perdichizzi (assistenti Coppolino e Baldaro), e tiene a battesimo il nuovo palazzetto dello sport, il PalaRescifina, più moderno ed accogliente del vecchio PalaTracuzzi (impianto nel quale per anni recitarono brillantemente la PCR e la Rescifina, due squadre di basket femminile che raggiunsero entrambe la serie A1, ma furono poi costrette a ridimensionare notevolmente le loro ambizioni). I dirigenti costruiscono una squadra di buon livello, che risponde in tono minore alle aspettative iniziali. Pur con alti e bassi, il grande basket inizia a transitare dalle parti dello Stretto, ma la risposta del pubblico rimane insoddisfacente. Nel roster Malcom Mackey, Chris Carrawell, l'australiano Simon Kerle, l'americano Richard "Scooter" Barry, gli italiani Mayer, Giuliani, Grappasonni e Cavalieri. Il gruppo conquista qualche vittoria di prestigio (contro Biella e Reggio Emilia) ed un sofferto approdo ai play-off (eliminazione subita da Napoli nei quarti di finale). Dopo questo primo anno di transizione, affidata la guida manageriale all'ex Montecatini Andrea Luchi, il complesso messinese viene totalmente rinnovato. Con un budget non elevatissimo, viene costruito un team capace di tenere testa a qualsiasi avversario. Il principale colpo del mercato giallorosso è l'acquisto di Brian Oliver, capocannoniere della serie A1 con la Viola Reggio Calabria nella stagione 1996/97, con 29 punti di media a partita. Le altre due stelle il play americano Lamarr Greer ed il centro portoricano Sharif Fajardo. Ai confermati Grappasonni e Cavalieri, si aggiungono gli italiani Foiera, Burini, Guerra e Vanuzzo. Fiore all'occhiello della società il settore giovanile (che conta già 300 iscritti), affidato a Pasquale Iracà. Luchi promuove numerose iniziative, volte a coinvolgere il pubblico messinese, e porta la squadra negli ospedali, nelle scuole ed al palazzo arcivescovile.
Il team (rinforzato in corso d'opera dall'arrivo di Saddi Washington) disputa un'entusiasmante regular season, conquistando il 2° posto alle spalle di Reggio Emilia. L'avventura dei giallorossi, costretti a rinunciare per infortunio alle stelle Greer e Fajardo, finisce nelle semifinali play-off, contro Napoli (che in finale riuscirà a beffare anche Reggio Emilia). Rimane il rimpianto per una serie affrontata dai giallorossi con evidenti difficoltà d'organico, ma anche la certezza che gli oltre 4.000 spettatori del PalaRescifina (accorsi per la sfida play-off contro i partenopei) sono la miglior base da cui ripartire….
La Pallacanestro Messina, nonostante il budget ridotto, riprova il salto di categoria nella stagione successiva. Trascinata dal confermato Oliver, dall'ex Cestistica Barcellona Marques Bragg (che si rivelerà uno dei migliori centri del torneo), da Herman Smith (prelevato dal Castelmaggiore) e dal nuovo play Leo Busca (arrivato in Sicilia da Udine), la squadra termina la stagione regolare al terzo posto. Nel corso del campionato arrivano Agostino Li Vecchi (in prestito, sempre dai friulani) e Mike Bernard (il gigante di Manchester). I giallorossi superano nei quarti di finale Pavia (3-1 il risultato finale della serie) ed in semifinale Castelmaggiore (ancora un 3-1 contro i bolognesi, che avevano eliminato a sorpresa Scafati), conquistando la finale per la promozione in massima serie. A cancellare le speranze di un approdo in A1 è la Sanic Teramo dell'intramontabile Mario Boni, che si aggiudica un'entusiasmante serie al termine di un'infuocata gara-5. Ai peloritani non basta il supporto di un centinaio di tifosi, accorsi in Abruzzo. La beffa finale non cancella le due serate che richiamarono al PalaRescifina quasi 10.000 spettatori per le due partite giocate in casa. In estate, gli attriti tra i proprietari e la mancanza di supporti economici spingono la società sull’orlo del fallimento. Dopo alcune settimane d'incertezza, la squadra viene catapultata a sorpresa in serie A: la FIP, infatti, esclude dalla massima serie la gloriosa Virtus Bologna e ripesca i giallorossi, che dimostrano di essere in possesso di tutti i requisiti richiesti dal Consiglio Federale. Quella peloritana è la seconda formazione dopo Trapani (che era stata nella massima serie nella stagione 1991/92) a portare così in alto il nome della Sicilia. E proprio la Regione lega il suo marchio alla squadra, divenendone sponsor principale (ma senza versare, nel corso dell’anno, i contributi promessi!).
Vengono confermati solo i tre italiani: il padovano Leo Busca, il catanese Seby Grasso –che lascerà presto Messina– e l’acrese Agostino Li Vecchi. Cambia anche il general manager: al posto di Andrea Luchi, che accetta la corte estiva della Scavolini Pesaro, approda in riva allo Stretto un altro ex Udine, Giancarlo Sarti. Piccolo lascia la presidenza all’ex amministratore delegato Caruso. In un mese viene costruito un team di ottimo livello, con stelle di prima grandezza, come Marlon Garnett (reduce da un anno di inattività) e Matt Bonner(uscito dalla Florida University). Dopo l’impresa dell’esordio con la Benetton Campione d’Italia (di fronte ad oltre 5.000 spettatori), arrivano 7 ko consecutivi che costano la panchina a Giovanni Perdichizzi (che nel ’91 aveva iniziato la sua esperienza da allenatore della Cestistica) ed il taglio a Bogojevic e Hill (risultato, oltretutto, positivo al THC). In panca viene chiamato l’ex allenatore della Skipper Bologna, Matteo Boniciolli. La serie da incubo si interrompe dopo 10 ko di fila, contro Teramo. Per risollevare una stagione iniziata malissimo, arrivano tre rinforzi: Brett Eppehimer, Vincent Yarbrough (ex Denver Nuggets) e Patrick Mutombo. Con 5 vittorie in 6 gare, i giallorossi lasciano dopo quasi tre mesi il fondo della graduatoria e concludono l’andata virtualmente salvi. Indimenticabile resta la serata di Milano: la Pallacanestro sbanca il Palasport delle mitiche "scarpette rosse" grazie ad una prestazione da extraterrestre di Marlon Garnett (38 punti con 8 triple da urlo).
Il girone di ritorno, però, è un calvario. All’indomani del ko con Roseto c’è un colpo di scena: coach Boniciolli, protagonista in campo e fuori (per aver denunciato la precaria situazione economica della società ed i ritardi nel pagamento degli stipendi), si dimette. La squadra è affidata a Pasquale Iracà, già vice del coach triestino ed assistente di Gaetano Gebbia alla Viola. Il tecnico reggino vede man mano sfaldarsi la creatura giallorossa. Primo atto la cessione di Li Vecchi alla FuturVirtus: un sacrificio necessario per rimpinguare le casse societarie ed alleggerire la busta paga da un oneroso ingaggio. Yarbrough, in occasione della sosta del campionato per le Final Eight di Coppa Italia, ottiene un permesso per recarsi negli States, ma non fa ritorno sullo Stretto per oltre 20 giorni. Nonostante le vittorie con Udine e Varese, le difficoltà extrasportive si accavallano: si dimette il presidente Caruso, falliscono le trattative tra i soci e le Istituzioni (Comune e Provincia) che volevano rilevare la società e la Questura, in seguito alla mancata installazione di una rete protettiva nel settore ospiti, dispone la disputa a porte chiuse per motivi di ordine pubblico del derby con Reggio Calabria! Il palasport desolatamente vuoto è l’emblema di una squadra abbandonata ad un triste destino. Termina la fuga di Yarbrough: l’americano rientrato dagli USA inscena, però, una lunga protesta e verrà messo fuori squadra. Questa decisione ed il mancato ritorno sul mercato condizioneranno irrimediabilmente la stagione di Messina, costretta a disputare la fase finale del torneo con un organico ridotto all’osso. L’impegno dello staff e la parziale copertura del budget da parte dei soci garantiscono appena la conclusione della stagione (dopo che la FuturVirtus di Sabatini era arrivata quasi ad acquisire il titolo di Messina). La retrocessione sul campo (con 15 sconfitte maturate nel girone di ritorno) è la logica conseguenza di una stagione gestita dalla società con approssimazione e inettitudine. Si chiude una stagione indecorosa, vissuta tra stipendi non pagati, ammutinamenti di squadra e staff, gravi carenze organizzative. Gli ingenti debiti societari (che sfiorano i due milioni di €) vanificano le trattative per la cessione del titolo di Legadue (per il quale aveva manifestato interesse il gruppo ligure dei Fertonani) e spingono la società verso il fallimento. Il 5 luglio, dopo la presentazione di una documentazione incompleta e la mancata ricapitalizzazione, la squadra viene cancellata dalla seconda lega nazionale. I protagonisti dell’ultima stagione si accasano altrove: il play Leonardo Busca, dopo due eccellenti stagioni sullo Stretto, si trasferisce a Ferrara, in Legadue; Marlon Garnett diviene la nuova guardia della Benetton Treviso; il congolese Mutombo viene scelto da Roseto; il centro Estill firma con Udine, Haslam con Livorno, mentre Yarbrough riparte dal Telindus Ostenda (la squadra belga nella quale si era trasferito l’ex coach Boniciolli). Matt Bonner disputa la " summer league e viene poi tesserato dai Toronto Raptors, l’unica squadra canadese della NBA. Il tecnico Iracà diviene assistente a Reggio Calabria, mentre Perdichizzi resta in provincia, a Capo d’Orlando (fresca ripescata in Legadue). Il 25 luglio il Consiglio Federale concede a Messina la possibilità di fondersi con una società di B, ma le trattative del Comune con la Spar Pesaro ed una squadra sarda non portano risultati. A listare a lutto le ultime pagine di questa vicenda è il decesso dell'ex presidente Caruso, colto da malore nel suo studio.
La città dello Stretto compie un balzo nel vuoto dalla prima alla sesta serie: la massima espressione dei canestri in città restano soltanto tre squadre dilettantistiche in serie C2. Il 9 dicembre 2004 arriva, infine, il fallimento della società, sancito da una sentenza del Tribunale di Messina. La triste parabola della Pallacanestro Messina continua ad avere ripercussioni: nei primi del 2005 il PalaRescifina viene anche chiuso al pubblico, perché inagibile. Il Curatore Fallimentare pone i sigilli alla tribuna collocata ai bordi del parquet ed agli uffici della società.