Fondata nel 1978, l'Orlandina Basket è stata tra le squadre più giovani come data di fondazione della Serie A 2007-08, rappresentando inoltre il comune più piccolo per numero di abitanti.
Esclusa nell'Ottobre 2008 dalla Serie A, nel 2009 riparte dalla Serie C Dilettanti ottenendo in due stagioni altrettante promozioni fino alla Serie A Dilettanti.

Dopo molti anni di attività in ambito regionale, nel 1996, dopo una retrocessione in Serie C2 con una sola vittoria su trenta incontri, venne rilevata dall'imprenditore Enzo Sindoni.

La Fiat Vinci Capo d'Orlando (poi Nebrodi Gas e dal 1998 Upea) vinse largamente il proprio campionato (29 vittorie su 30 incontri) e l'anno successivo bissò il successo in Serie C1 (26 vittorie su 30 incontri) raggiungendo la Serie B2.

Nella stagione 1998-1999 arrivò come nuovo playmaker Alessandro Fantozzi, ex giocatore della nazionale. La prima stagione del livornese non fu esaltante: l'Orlandina, dopo un settimo posto nella stagione regolare, venne eliminata nel primo turno dei play-off da Trapani; nella seconda però il suo apporto fu determinante per la promozione in Serie B1.

Al termine della stagione 2000-01 arrivò la seconda promozione consecutiva: l'Orlandina conquistava la Legadue attraverso i playoff dopo un secondo posto nella stagione regolare.

Nel 2001-02 la squadra ottenne un'agevole salvezza, ma il sogno si infranse la stagione successiva, quando l'Upea retrocesse in Serie B1. Nell'estate 2004, grazie ad un incredibile ed insperato ripescaggio, la società di Enzo Sindoni ritornò in Legadue. Nella stagione 2004-2005, con Giovanni Perdichizzi in panchina, l'Orlandina perse appena tre partite e venne promossa da prima in classifica in Serie A1.

A febbraio vinse anche la Coppa di Legadue. È così diventata la quinta squadra siciliana a giocare nella massima divisione, la terza nel dopoguerra. Dopo gli anni '40 con Giglio Bianco Catania e Palermo, infatti, negli anni '90 e 2000, hanno militato in serie A per una sola stagione Trapani e Messina.

Battute iniziali di Orlandina-Cantù al PalaFantozzi Nel 2005-06 si salvò all'ultima giornata, diventando la prima squadra siciliana a conservare la categoria per più di una stagione. Nel 2006-07 il presidente Sindoni, neo sindaco di Capo d'Orlando, è costretto a ricostruire da zero la squadra, ripartendo da Perdichizzi e con le uniche conferme di Esposito e Fabi.

La squadra, che lotta a lungo per i play-off, si salvò nuovamente all'ultima giornata pur perdendo lo scontro diretto di Roseto. Nel 2007-08 il presidente Sindoni ingaggiò Gianmarco Pozzecco, medaglia d'argento alle Olimpiadi di Atene 2004 e giocatore di valore assoluto. Importanti anche gli acquisti degli americani Wallace, Slay e Diener, e il ritorno di Howell, uno degli artefici della promozione in A1.

Durante la preparazione estiva, l'Orlandina Basket arriva in finale del "Memorial Carone" e si aggiudica il torneo amichevole "Lo Forte". In entrambe le manifestazioni la finale è stata giocata contro i serbi del Partizan Belgrado. Al termine del girone d'andata la squadra si aggiudicò il diritto a partecipare alla Final Eight di Coppa Italia, venendo eliminata ai quarti di finale da Biella.

Ceduto il realizzatore Diener a Siena, l'Orlandina Basket piazzò altri due importanti colpi sul mercato, ingaggiando Beck da Varese e il giovane Mejia dalla D-League; questi innesti, oltre al recupero di Colin Falls, sono stati decisivi per il mantenimento delle posizioni alte della classifica.

Il 17 aprile 2008, ancora contro Biella, l'Orlandina Basket scrive un'altra pagina della sua storia cestistica conquistando per la prima volta l'accesso ai play-off scudetto, grazie alla vittoria esterna sul campo dei piemontesi, e concludendo la regular season al sesto posto finale. Il quarto di finale vede Avellino vincere la serie 3-0, dopo 3 gare molto combattute. La partita che sancisce l'eliminazione dai play-off dell'Orlandina Basket è anche l'ultima gara di Gianmarco Pozzecco, indiscusso leader della squadra, che chiude così la carriera.
I risultati degli altri quarti di finale consentono comunque all'Orlandina di ottenere la storica qualificazione all'Eurocup. La stagione 2008-09 non viene disputata dall'Orlandina poiché il 20 settembre 2008, il consiglio federale annuncia l'esclusione della società dal campionato.

Prima del fallimento (e del conseguente scioglimento dei contratti) il roster della squadra era guidato da Romeo Sacchetti ed era composto dai seguenti giocatori: Tyus Edney, Gabriele Ganeto, Klaudio Ndoja, Tony Binetti, Phil Martin, Samuel Haanpää, Simone Flamini, Francesco Orsini, Drake Diener, Adam Wójcik, Nik Caner-Medley, Greg Brunner, Colin Falls, Antonio Fazio.

L'attività della società riparte nel 2009-2010, quando la Pallacanestro Nebrodi, squadra di Capo d'Orlando che nella stagione precedente aveva disputato il campionato di Promozione chiudendo all'ultimo posto, viene ammessa in Serie C Dilettanti grazie all'accoglimento della domanda di ripescaggio presentata alla Lega Nazionale Pallacanestro in sostituzione della Folgore Nocera e ottenendo il cambio di denominazione in Orlandina Basket.

La stagione si conclude con il primo posto e la promozione in Serie B Dilettanti con sei turni di anticipo. Tra i cestisti che hanno disputato la stagione 2009-2010 con la maglia dell'Orlandina vi sono Giuseppe Costantino e Gianmarco Pozzecco il quale ha disputato una gara dopo due anni dal ritiro dalla pallacanestro professionistica.

Nella stagione 2010-2011, dopo il primo posto raggiunto nella stagione regolare nel girone D di Serie B Dilettanti, l'Orlandina Basket ottiene la promozione in Serie A Dilettanti vincendo la serie della finale play-off (2-1) contro la Viola Reggio Calabria.