Rex Linn nasce a Spearman, nella contea di Hansford, terzo figlio di Darlene (nata Deere) e James Paul Linn.[1] In questa piccola comunità del Texas, già in tenera età, Linn sviluppò un profondo interesse per il cinema e la recitazione. Il Lyric Theater di Main Street (che è tuttora in funzione) era l'unico cinema di cui gli abitanti di Spearman potessero usufruire nell'intera area, e Rex fin da giovane frequentava spesso questo cinema, godendo del suo menu di film horror e western.
Nel 1969 la famiglia Linn si trasferì ad Oklahoma City, la capitale dell'Oklahoma, dove il padre esercitò la professione legale. Qui frequentò la Heritage Hall e poi la Casady School, una scuola indipendente affiliata alla Chiesa episcopale, e lavorò part-time presso l'Oklahoma City Zoo. Fu nel 1975 che, dopo aver visto Jack Nicholson nel filmQualcuno volò sul nido del cuculo, decise che voleva veramente diventare un attore. Durante il liceo il suo sogno fu messo in seria difficoltà: durante la prima serata della produzione scolastica di Fiddler on the Roof, Rex aveva infatti quasi demolito un set nel corso di un numero di danza e gli fu chiesto di lasciare la produzione dal suo insegnante di recitazione. Gli fu consigliato di usare le sue energie in qualche altro campo della ricerca, e ciò porto alla fine della sua carriera recitativa scolastica. Nel 1980 si laureò in Radio/TV/Film alla Oklahoma State University-Stillwater.
Dopo essersi laureato, Linn intraprese la carriera bancaria. Lavorò per la Lakeshore Bank fino al 1982, quando la banca venne chiusa per insolvenza. Convinse quindi un talent scout a rappresentarlo nel mercato dell'Oklahoma e allo stesso tempo accettò un lavoro con una compagnia petrolifera, per la quale doveva supervisionare le operazioni sul terreno nell'Oklahoma occidentale. Dopo aver preso parte ad alcuni spot pubblicitari di bassa fattura, iniziò a recitare in piccoli ruoli in vari progetti. La sua prima partecipazione in un film la ottenne nel 1986 in Shadows on the Wall. Successivamente (dopo aver recitato nel film televisivo Bonanza: The Next Generation) partecipò a un altro film, dal titolo Dark Before Dawn, prodotto dal suo amico Edward K. Gaylord II. Fu proprio grazie a lui che riuscì a ottenere anche il ruolo di produttore associato del film, esperienza che gli fornì grande intuizione nel processo creativo di un film e che gli sarà successivamente molto utile per la sua carriera recitativa.
Il 29 giugno 1994 è stato onorato con una stella nel Carpenter's Square Theatre Walk of Fame di Oklahoma City.
Tra il 2005 e il 2006 ha prestato la sua voce a tre audiolibri: One Ranger (2005), A Man Called Cash (2005) e Missing Persons (2006). In precedenza aveva inoltre prestato la sua voce come narratore di un documentario per il programma dell'Oklahoma University InvestEd dal titolo Anatomy of Fraud – Catching a Con in Pottawatomie County in 2004.
