Rudi wuchs in einer kinderreichen Familie auf (16 Geschwister) und begann mit 11 Jahren bei Stainz mit dem Fußballspielen. Als 19jähriger wechselte er zum SC Deutschlandsberg und schließlich zum GAK. Für die Grazer kam er bei 14 Bundesligaspielen zum Einsatz und erzielte dabei 1 Tor. Im Mai in Salzburg-Lehen traf er kaum eingewechselt (72.) drei Minuten später zum 2:1-Sieg für die Athletiker.
1980 holte Rapid das Talent nach Hütteldorf. In 42 Spielen gelang ihm aber kein Tor für die Grün-Weißen, holte aber 1982 den Titel mit Rapid. Von Trainer Krankl bekam er den Spitznamen "Der Panzer". Allzu wohl hat er sich in Wien nicht gefühlt, dafür lernte er dort seine spätere Gattin kennen. Nach zwei Jahren kehrte er zum GAK zurück, wo er vier Jahre Stammspieler war und es sogar zum Teamehren schaffte. 1985 debütierte er beim Freundschaftsspiel in Saragossa gegen Spanien, wo er beim 0:0 in der 61. Minute für Walter Hörmann aufs Feld kam. Zweimal kam er noch zu Einsätzen im Nationalteam, Im Mai 1986 wurde er beim 1:0 gegen Schweden in der 87.Minute für Lainer eingewechselt, sowie im März 1987 beim 0:4 in Banja Luca gegen Jugoslawien, wo er die zweite Spielhälfte statt Piesinger spielte. Dies bereits als Tirol-Spieler.

Im Sommer 1986 klopfte nämlich der FC Swarovski beim GAK an und holte Rudi Steinbauer nach Innsbruck, wo er zum "Turbo-Rudi" wurde. Zwei wechselhafte Jahre verbrachte Rudi in Innsbruck. Erste Saison Dritter in der Meisterschaft im ÖFB-Cup im Finale und im UEFA-Cup im Halbfinale, Stammspieler unter Trainer Latzke. Im Herbst 1987, dann im ersten Liga-Spiel verletzt, die halbe Herbstsaison ausgefallen. Mit dem FCS unter Ernst Happel gerade noch die Qualifikation für das Meister-Play-Off geschafft, im ÖFB-Cup wieder im Finale, aber an Krems gescheitert.
1988 ging er nach St.Pölten und unterschrieb für die "Wölfe", der VSE war gerade in die Bundesliga aufgestiegen. Bis 1994 war er mit den Hauptstädtern in der Bundesliga, nach dem Abstieg ging er zurück zum GAK mit dem er 1995 als Meister wieder in die 1.Division der Bundesliga zurückkehrte.