Polster came through the Austria Wien youth system to make his professional league debut in August 1982, at 18 years of age. He scored his first Bundesliga goal three weeks later and went on to win three league titles and a domestic cup before moving abroad to play a season for Serie A mid-table side Torino. He then spent the five following years at Spanish teams Sevilla, Logroñés and Rayo Vallecano, ending up with these teams in mid-table as well. In 1990, he finished runner-up in the Spanish goalscoring chart. In 1993, he moved to Germany to spend five years at Köln, again ending up in mid-table every season except for the last one in which he experienced relegation. That made him join Borussia Mönchengladbach next year but they got also relegated at the end of the season and Polster returned to Austria to play a final season at Austria Salzburg.
He was known to fans as "Doppelpack" Polster – "Twinpack" Polster, because of his reputation for scoring two goals in many matches.
He had already made his senior debut for Austria in November 1982 against Turkey, immediately scoring his first goal, and was a participant at the 1990 World Cup and 1998 World Cup. He earned 95 caps, scoring a record 44 goals. He overtook the previous goalscoring record, set by Hans Krankl, in November 1996, scoring his 35th goal against Latvia.
Polster began his coaching career in January 2010 as the reserve-team coach at LASK Linz. In June 2011, he became the head coach of SC Wiener Viktoria in the Austrian 2. Landesliga, the fifth-tier in Austrian football. During his first season at Wiener Viktoria, the team promoted to the fourth-tier and consequently a year after to the third division, the so-called Austrian Regional League. On 17 June 2013, he accepted his first coaching role in the Austrian Bundesliga, taking over as the head coach of the top-flight side Admira Wacker Mödling. After starting the season with three straight defeats, including a 7–1 defeat to newly promoted Scholz Grödig, Polster was fired by Admira on 9 August 2013. Polster returned to SC Wiener Viktoria on 13 January 2014.