Mathis iniziò la sua carriera professionistica nei New York Titans della American Football League, con cui rimase tutta la carriera. Uno dei quattro Titans ad essere rimasti con la franchigia quando i Jets vinsero a sorpresa il Super Bowl III contro i Baltimore Colts[1], Mathis guidò la American Football League in corse nel 1961, venendo inserito da Sporting News nella formazione ideale della lega quell'anno. Fu convocato per l'All-Star Game nel 1961 e 1963. Mathis si ruppe una vertebra nella terza gara del 1961, contro i Boston Patriots. Riuscì tuttavia a scendere in campo nella partita successiva e non perse una sola gara quell'anno. Quella resistenza gli consentì di mantenere il proprio posto nel roster anno dopo anno, concludendo la sua carriera nel 1969. È uno dei soli venti giocatori ad avere giocato nella AFL per tutti i dieci anni della sua esistenza e uno dei soli sette ad averlo fatto con una sola franchigia.
Stati Uniti
Clemson Tigers
New York Jets
Campionati AFL : 1
Super Bowl : 1
