Mathis was born in Gainesville, Texas, and attended Gainesville High School, where he lettered in football, basketball, and track. In football, he was a two-time All-District selection. He accepted a football scholarship from Texas A&M University-Commerce. As a redshirt freshman, he was a backup cornerback, tallying 64 tackles, 3 interceptions, 11 passes defensed and 4 fumble recoveries. As a sophomore he was named a starter at cornerback, registering 57 tackles, 3 interceptions, 13 passes defensed and 3 forced fumbles As a junior, he collected 55 tackles, 6 interceptions and 16 passes defensed, while having 26 punt returns for a 10.4-yard average and 11 kickoff returns for a 24.6-yard average. As a senior, he recorded 48 tackles, 4 interceptions, 17 passes defensed and one sack. He led the team with 16 punt returns for a 9.7-yard average and 15 kickoff returns for a 24.9-yard average. In 2009, he was inducted into the Texas A&M-Commerce Athletic Hall of Fame.
Mathis was signed as an undrafted free agent by the Dallas Cowboys after the 1997 NFL Draft, after dropping because of his size and small college background. He would end up making the team after taking advantage of Deion Sanders being away while playing professional baseball and displaying his track speed. As a rookie, he played in all 16 games, recorded 23 tackles, 5 passes defensed, one forced fumble, one fumble recovery, 12 special teams tackles and also returned punts. He started the final 3 contests at right cornerback, following Sanders' season ending rib fracture injury. In 1998, he was moved to the left side to backup Kevin Smith. At the end of the season, he passed an injured Smith on the depth chart, starting the final 4 games of the season and the wild card playoff loss against the Arizona Cardinals. He also established himself as one of the more productive kickoff returners in the league, averaging 24.8 yards to finish ranked sixth in the NFC. He posted 41 tackles, 2 interceptions, 8 passes defensed, one forced fumble, 2 fumble recoveries and special teams tackles. He missed 3 games with a broken right forearm. In 1999, he would miss 8 games because of knee and hamstring injuries. He had 4 starts, but was mostly a backup behind Smith and Charlie Williams. In 2000, the Cowboys had a lot of turnover at linebacker and one of the moves made to improve the depth was trading Mathis to the New Orleans Saints in exchange for linebacker Chris Bordano on April 26. Also factoring in the decision was his injury history and the numbers at the cornerback position.
On September 17, 2002, Mathis was signed as a free agent by the Atlanta Falcons. He played 11 games in the nickel packages, registering a career-high 3 interceptions. He started 12 games in 2004, finishing with 67 tackles and 2 interceptions. On September 13, 2005, he was lost for the season with a career-threatening left knee injury, after tearing 3 ligaments during a practice drill. The next year, he returned to play but suffered a career-ending neck injury, while tackling Eddie Drummond on the opening kickoff against the Detroit Lions on November 5, 2006. He was released injured on April 9, 2007.
