After spells with various small clubs in East Germany, Heinrich joined amateur side Kickers Emdenin the summer of 1990 and played for the club in the following four seasons, three of which were in the third division. In the summer of 1994, he left Kickers Emden for Bundesliga side SC Freiburg and started his professional career at the club. He made his Bundesliga debut on 20 August 1994 as a second-half substitute in SC Freiburg's opening match of the 1994–95 Bundesliga season, a 2–0 defeat away against Karlsruher SC. He went on to become a regular in the Freiburg team during his first season with the club and appeared in 33 out of possible 34 Bundesliga matches that season, also scoring seven goals for the club in the league and helping the team to a surprising third-place finish in the Bundesliga that season. He scored his first Bundesliga goal already in his second appearance for SC Freiburg in the league, netting the final goal in the club's surprising 5–1 home victory over FC Bayern Munich. He appeared in another eight Bundesliga matches for SC Freiburg in the following season and went on to leave the club for Borussia Dortmund in January 1996. He went on to appear for Borussia Dortmund in all 17 Bundesliga matches until the end of the 1995–96 season and also won the Bundesliga champions title with the club that season. He was also a regular in the following two seasons, appearing in 64 out of possible 68 Bundesliga matches. He scored 11 Bundesliga goals for Borussia Dortmund in two and half seasons with the club. In 1997, he also won the UEFA Champions League with Borussia Dortmund, playing all 90 minutes in their 3–1 victory over Juventus Turin in the Final. In the summer of 1998, Heinrich moved to Italian club ACF Fiorentina and continued to play there in the following two seasons before returning to Borussia Dortmund in the summer of 2000. In two seasons with Fiorentina, he made 57 Serie A appearances and scored five goals for the club in the league. He subsequently played three seasons for Borussia Dortmund, but was a regular only in the first of these three seasons. In 2002, he won another Bundesliga champions title with the club. Between 2000 and 2003, Heinrich made 63 Bundesliga appearances for Borussia Dortmund and scored seven goals for the club in the league. He also participated with Borussia Dortmund in the 2002–03 UEFA Champions League season and made seven appearances in the competition. In the summer of 2003, Heinrich left Borussia Dortmund for 1. FC Köln and appeared in 20 Bundesliga matches for the club in the following season before finishing his professional career in the spring of 2004. He played his last Bundesliga match in 1. FC Köln's 3–0 defeat away against SC Freiburg, his first professional club, on 27 March 2004. After retiring from professional football, he continued to play as an amateur in the fourth-division Oberliga NOFV-Nord, spending one season with Ludwigsfelder FC and one half-season with 1. FC Union Berlin, where he finished his playing career in December 2005 and continued to work for the club as their sports director. Since August 2006, he also plays occasionally for fifth-division side TSV Chemie Premnitz. Heinrich was also a member of the German national team between 1995 and 2002, winning 37 international caps and scoring two goals for the team. He made his international debut in Germany's friendly match against Italy on 21 June 1995. He was a member of the German squad at the 1998 World Cup finals in France and appeared in all five matches before the team was surprisingly eliminated by Croatia in the quarterfinals. He also appeared for Germany in all of their three matches at the disappointing 1999 Confederations Cup in Mexico, where the team was eliminated in the group stage.
