פולסטר שיחק בקבוצת הנוער של אוסטריה וינה, בה ערך את הופעת הבכורה שלו בבוגרים באוגוסט1982, בגיל 18. הוא כבש את שערו הראשון בליגת העל האוסטרית שלושה שבועות אחר כך במדי קבוצתו, עימה זכה 3 תוארי אליפות רצופים וגביע אחד באוסטריה, לפני שעבר לשחק מחוץ למדינתו בקבוצת מרכז הטבלה של הסרייה א' באיטליהטורינו. אחרי ששיחק עונה אחת באיטליה, הוא עבר לשחק במהלך חמש העונות הבאות במועדונים הספרדיםסביליה, CD לוגרונייס וראיו ואיקאנו, אשר גם בקבוצות הללו סיים את העונות במרכז הטבלה של הליגה. בשנת1990, הוא סיים במקום השני בטבלת כובשי השערים של הלה ליגה.
בשנת 1993, הוא עבר לשחק בבונדסליגה הגרמנית בה בילה חמש שנים בקבוצת פ.צ. קלן, עימה סיים את ארבע העונות הראשונות שלו בקבוצה במרכז טבלת הליגה ובעונה האחרונה שלו עימה ירד ליגה. בעקבות ירידת הליגה של קלן, פולסטר עבר לשחק בשורות בורוסיה מנשנגלדבך לעונה אחת, אבל לצערו גם במדי קבוצתו החדשה בגרמניה חווה ירידת ליגה, ששוב גרמה לו בסיום העונה לעבור קבוצה. הוא חזר לשחק באוסטריה, בה שיחק את עונתו האחרונה בקבוצת אוסטריה זלצבורג.
לאוהדיו הרבים באוסטריה יש הרבה כינויים לשמו של פולסטר, כאשר רובם מציינים את יכולת כיבוש הצמדים המרשימה שלו, לאחר שבלא מעט משחקים שלו כבש פולסטר צמד שערים. במהלך הקריירה שלו באוסטריה, זכה פולסטר 3 פעמים בתואר מלך השערים של הליגה האוסטרית (1985, 1986, 1987) פולסטר נבחר לנבחרת המאה של אוסטריה בשנת 2001.
בשנת 1983, פולסטר זומן לנבחרת אוסטריה עד גיל 20, לשחק בשורותיה במסגרת אליפות העולם לנבחרות נוער באותה השנה.
הוא ערך את הופעת הבכורה שלו בנבחרת הבוגרת של אוסטריה כבר בנובמבר 1982 נגד נבחרת טורקיה, ובאותו משחק אף כבש את שערו הראשון בנבחרת. פולסטר היה חלק מסגל הנבחרת האוסטרית במהלך טורנירימונדיאל 1990 ומונדיאל 1998. הוא שיחק במדי הנבחרת הלאומית 95 משחקים, בהם כבש שיא כיבושים אוסטרי בסך 44 שערים. הוא שבר את השיא הקודם של הנס קרנקל שעמד על סך 34 שערים, אחרי שהבקיע את שערו ה-35 בנבחרת בשנת 1996, במשחק נגד לטביה.
פולסטר ערך את הופעתו הרשמית האחרונה בנבחרת (בה קבע שיא הופעות אוסטרי חדש, עם 94 משחקים) ביולי 1998, במסגרת מונדיאל 1998, נגד איטליה. אחרי שנתיים, הוחלט לערוך לכבודו משחק פרידה נוסף, בספטמבר2000, נגד איראן, בו הוחלף בדקה ה-21 של המשחק על ידי כריסטיאן מאיירלב. שיא ההופעות הבינלאומי שלו (95) נשבר על ידי אנדריאס הרצוג במאי 2002.
אתר האינטרנט הרשמי של טוני פולסטר
