Mathis played well in his first season in Germany, scoring on his debut and went on to score four goals in his first five games. But soon after, his manager was fired and replaced by Ewald Lienen. In his second Bundesliga season, Lienen often kept Mathis on the bench. On September 25, 2004, upon entering Hannover's match against Schalke as a very late substitute, Mathis scored the game-winning goal almost immediately. In celebration, he ran to the sideline and tapped his watch at Lienen. Mathis escaped being fined for the outburst and later confirmed the gesture was meant the way it was widely interpreted - that Lienen should have played him earlier. He started the next game but afterwards never played with the first team again. In December, he was transferred back to MLS, joining expansion club Real Salt Lake.