Figlio di un allenatore di basket di livello collegiale Houston ha sempre avuto grande familiarità con il mondo del basket, e la volontà di giocare da professionista. Frequenta il college a Tennessee University e si dichiara eleggibile per il draft NBA 1993. Viene scelto al primo giro come undicesima chiamata assoluta dai Detroit Pistons. I Pistons sono appena usciti dalla ricostruzione successiva ai due titoli vinti nel 1989 e nel 1990 e la squadra è di basso livello. Nel complesso la prima stagione di Houston è incolore con 8,5 punti a partita e poco altro. Nella stagione 1994-95 con il Rookie of The YearGrant Hill la situazione di squadra non cambia, ma si individua la strada da tenere per risalire. La media punti di Houston sale a 14,5 e comincia a giocare saltuariamente in quintetto. L'anno dopo finalmente arriva la qualificazione ai play-off, con Houston che diventa il secondo marcatore di squadra e conquista stabilmente il ruolo di Shooting guard in quintetto. Nella post season però i Pistons vengono eliminati in solo tre partite dagli Orlando Magic.
L'approdo a New York
I Pistons vedono un grande futuro con la coppia Hill-Houston, ma nell'estate del 1996 Allan è free agent e dai New York Knicks arriva un'offerta che non è possibile rifiutare; dalla stagione 1996-97 Houston veste così la maglia numero 20 dei Knicks. I Knicks sono una squadra molto forte, che nell'estate del 1996 ha allestito una formazione per vincere il titolo. Houston ricopre il ruolo di guardia titolare. Rispetto a Detroit la sua media punti passa da 19,7 a 14,8, questo perché ci sono varie stelle tra cui dividere i tiri, e il gioco dei Knicks è incentrato su Patrick Ewing. Nei play-off i Knicks eliminano i Charlotte Hornets in tre partite. Al secondo turno incontrano i Miami Heat: tra le squadre ci sono degli attriti e in gara-5 scoppia una rissa che costa ai Knicks la squalifica di buona parte della squadra; il provvedimento per gli Heat è più leggero e Miami riesce a vincere la serie in sette gare. Nonostante la delusione i Knicks sono decisi a riprovarci l'anno dopo. Nella stagione regolare però un infortunio occorso a Ewing tiene fuori dal centro di New York per buona parte della stagione. Houston diventa così il migliore marcatore della squadra con 18,4 punti a partita. Nei play-off i Knicks si prendono una rivincita eliminando al primo turno gli Heat in 5 combattute partite. Al secondo turno si devono però arrendere agli Indiana Pacers in 5 partite.
La finale e la coppia Houston - Sprewell
L'anno dopo con l'addio di due colonne della storia dei Knicks come Charles Oakley e John Starks, con il calo di rendimenti di Ewing e Larry Johnson, la squadra sembra destinata, nonostante l'arrivo del rientrante Latrell Sprewell a un campionato incolore. Al primo turno i Knicks incontrano ancora gli Heat che sono però decisamente favoriti essendo la miglior squadra della Eastern Conference. I Knicks vincono gara-1, ma perdono gara-2. Al Madison Square Garden vincono gara-3 ma Alonzo Mourning permette ai suoi di giocarsi gara-5 in casa. In gara-5 a quattro secondi dalla fine gli Heat sono avanti di 1 e Houston ha palla in mano. Perde il controllo, ma riesce ad ottenere la rimessa. New York non ha più time-out ma ha un gioco per l'occasione: Houston riceve palla, scocca un tiro che colpisce il primo ferro impennandosi e finendo nel canestro. La vendetta di due anni prima è definitivamente consumata. Galvanizzati da questa vittoria i Knicks cavalcano nei play-off, eliminando gli Atlanta Hawks e i Pacers. Arrivano in finale, ma nella cavalcata della post season la squadra ha perso diversi elementi. Ewing e Johnson si infortunano e i Knicks devono affrontare i San Antonio Spurs della coppia Duncan - Robinson privi dei loro lunghi. Arriva così una sconfitta per 4-1.
La finale di Conference e gli ultimi anni
L'anno dopo il baricentro dei Knicks si sposta definitivamente da Ewing alla coppia di esterni Houston-Sprewell. New York prova a ripetere l'impresa dell'anno prima, ma dopo aver eliminato i Toronto Raptors e ancora una volta i Miami Heat, si devono arrendere a Reggie Miller e ai suoi Pacers. Nella stagione 2000-01 va ancora peggio: Ewing se ne è andato e nonostante Houston sia ormai asceso al ranking di stella NBA, i Knicks non vanno oltre l'eliminazione al primo turno per mano dei Raptors. Dal punto di vista individuale questi sono i migliori anni della carriera di Houston ma i risultati di squadra non l'appoggiano; I Knicks restano anche fuori dalla post season. Nella stagione 2003-04 un infortunio costringe Allan a giocare solo 50 partite su 82 e a sottoporsi ad un intervento chirurgico. Prova a tornare l'anno dopo quando gioca 20 partite, ma tutti si accorgono di come le sue gambe abbiano perso l'esplosività di un tempo. Per non diventare l'ombra del giocatore che era decide di ritirarsi. L'ultima sua stagione è così stata quella del 2004-05.
La stagione 2007-08
Il 10 ottobre del 2007 la sua ultima squadra, New York, lo prende come free agent, per poi tagliarlo dieci giorni dopo.
La stagione 2008-09
Il 26 settembre del 2008 firma ancora per i New York un contratto da free agent, ma al termine della pre-season, senza mai scendere in campo, viene tagliato dalla dirigenza per entrare nello staff della società.
Vita extracestistica
Nel 1999 ha recitato nel film Black & White, nel quale interpreta la parte di un giocatore corrotto.
