Born in Vienna, Herzog started his career at local giants Rapid Vienna, but was sent out on loan to city rivals First Vienna FC during 1987–88. That move proved to be successful and he was soon recalled to Rapid to start the 1988–89 season. He made his name at Rapid in the next years to secure a move to Bundesliga side Werder Bremen where he would spend eight years, divided in two periods by a season at Bayern Munich where he won the UEFA Cup, beating Girondins de Bordeaux in a two-legged final.
After returning to Rapid in 2002, he decided to end his career with Major League Soccer franchise Los Angeles Galaxy in 2004. Under head coach, Sigi Schmid, Herzog played well but following a mid season coaching change, Herzog saw his playing time decrease and at the end of the season, he retired.
A stylish attacking midfielder, Herzog was well known for his ability to score stunning free-kicks. He captained the Rapid Wien side and was chosen in Rapid's Team of the Century in 1999.
He made his debut for Austria in an April 1988 friendly match against Greece and was a participant at the 1990 and 1998 World Cups. In World Cup 98 he scored a penalty goal against Italy. He earned 103 caps, scoring 26 goals, which makes him Austria's most capped player of all-time. He surpassed striker Anton Polster in May 2002 when winning his 96th cap. His last international was an April 2003 friendly match against Scotland.