Nell'autunno del 1995 Willie Salazar, Damon Delapaz ed un altro ragazzo formano nella zona nord di Houston, nel Texas, un gruppo, i Riverfenix, di cui diventano rispettivamente i primi due chitarristi ed il terzo cantante. Presto arrivano a completare la line-up Adam Lewis al basso e Donnie Reyes alla batteria, mentre il cantante in seguito ad un incidente è costretto a lasciare la band, sostituito alla voce da Willie, che comunque continua a suonare la chitarra. Iniziano così a fare dei tours raccogliendo un buon seguito di fans in tutti gli Stati Uniti, e a San Diego, dove la band presto si trasferisce, la loro fama arriva alle orecchie di Mark Hoppus dei Blink 182, che diventa il loro manager. Sempre a San Diego firmano un contratto con la Drive-Thru Records, una casa affiliata con una la major MCA Records (nel senso che la MCA ha diritto di precedenza su ogni altra etichetta di mettere sotto contratto una band della Drive-Thru), una sotto casa della Universal Music Group, per la quale esce nel '97 l'album omonimo, il cui singolo "Speechless" viene molto apprezzato. La band deve cambiare però nome, per evitare possibili conflitti legali con l'attore River Phoenix, trasformandosi così in Fenix*Tx, in omaggio al loro stato (TX è la sigla del Texas). Sotto questo nome la MCA, in collaborazione con la Drive-Thru, ristampa nel '98 l'album di debutto, che cambia titolo rimanendo però omonimo (si chiama Fenix*Tx, in quanto è cambiato anche il nome del gruppo), aggiungendovi due inediti. Il brano "All My Fault" viene messo anche in scaletta sugli schermi di MTV, e la crescente popolarità porta il gruppo a partecipare al Blink 182/Bad Religion Summer Tour del 2000. A questo punto Donnie decide di andarsene e alla batteria passa così il chitarrista Damon (aveva già suonato come batterista in alcuni concerti dei Blink 182, quando il loro batterista Travis si era infortunato durante un tour), sostituito nel ruolo di chitarrista da James Love, già tecnico delle chitarre della band. Esce con questa formazione, nel 2001 e sempre in collaborazione tra Drive-Thru e MCA, "Lechuza", nome tratto da una leggenda dei loro popoli d'origine (tutti i membri della band sono metà spagnoli e metà caucasici). Lechuza nella loro lingua madre significa gufo, ma vi è una leggenda parla di un essere mezzo strega e mezzo gufo che la notte cerca bambini, che misteriosamente scompaiono. Il tour di promozione del nuovo album li porta nel 2001 anche a partecipare all'annuale edizione del Vans Warped Tour.