Door zijn vader Ton, die pas op 37-jarige leeftijd aan wielerwedstrijden begon deel te nemen, kwam de op 31 januari 1966 in Amsterdam geboren Tonnie Teuben in aanraking met het wielrennen. Op viertienjarige leeftijd werd hij lid van Olympia en begon bij de jeugd. Daarvoor voetbalde hij vier jaar bij Heerenveense Boys. De eerste keer dat Teuben op het podium kwam was bij de provinciale kampioenschappen in het Drentse Eext in 1981. Bij de nieuwelingen werd hij derde, na Eddy Schurer en Wim Procee. Een jaar later veroverde hij te Nieuweschans de Friese titel in die categorie, terwijl een week later de Ronde van Garijp op zijn erelijst kon worden bijgeschreven. Niet alleen op de weg was Tonnie Teuben rap, maar ook in het veld moest rekening met hem worden gehouden. In 1983 veroverde hij te Drachten de Friese cyclo- cross-titel bij de junioren. In 1985 werd Teuben amateur, verliet Olympia Heerenveen en werd lid van de Amsterdamse wielervereniging Olympia. In dat jaar won de toen dienstplichtige militair zijn eerste amateurcriterium te Kootstertille. Vooral bij de amateurs wist hij in de criteriums menige prijs in de wacht te slepen, maar het belangrijkste waren voor hem de klassiekers. Zo schreef hij in 1986 in het Drentse Schoonebeek de Omloop van het Olieveld op zijn naam. "De rondjes om kroeg en kerk zijn wel leuk, maar als je ambities hebt om verder te komen moet je in de grote wedstrijden starten", was zijn mening. Via Ulysses en de Friese Bioform-selectie tekende hij een contract bij de sponsorploeg van Koga Miyata. In zijn eerste jaar behaalde hij er veertien overwinningen, waaronder primus in de Ronde van Groningen. Het boterde echter niet tussen hem en ploegleider Egbert Koersen, waarna de renner uit Hee- renveen uitkwam voor Teleflex. Daar had hij een bijzonder slecht seizoen. "Volgens mij kwam dat doordat ik naar een studentenwoning verhuisde. Feesten vierde hoogtij en slapen was bij- zaak", aldus Teuben. Maar in 1992, in het shirt van PWZ Emmen (Promotie Wielersport Zuiderveld) o.l.v. Herman Snoeijink, kwam het herstel. De Ronde van Overijssel en de Grote Prijs Wieler Revue werden aan zijn palmares toegevoegd. In 1993 keerde hij terug naar Olympia, waar hij samen met ondermeer Ludo Rinzema, Kees van den Akker, Henk Gijzen, Thijs de Vries, Jan van Berkum en Sierd Steigenga domineerde in de promotiecompetititie. Op een haar na miste men promotie naar de topcompetitie. In 1994 veranderde hij voor de zoveelste maal van ploeg en tekende voor de sponsorformatie Löwik/De Zwaluwen, waarna hij in juli 1995 prof werd.
Een profcontract zat er aanvankelijk niet in. Weliswaar waren er in 1988, toen Teuben maar liefst dertien zeges boekte en tot koning van de Friese criteriums werd gekroond, contacten met de Spaanse formatie Caja Rural, met de Nederlander Albert Stofberg als ploegleider, maar tot een contract kwam het niet. In 1992 toonde Hennie Kuiper serieuze belangstelling voor Teuben. De financiële onzekerheid bij sponsor Motorola deed ook nu de overstap naar de broodrijders niet doorgaan. Pas in 1995 werd hij, gesponsord door Farnholt, beroepsrenner, maar een half jaar later keerde de Heerenveener al weer terug naar de rijen der amateurs van Olympia. Zijn beste profprestaties boekte de intussen naar Nijelamer verhuisde coureur in de eigen regio: 3e in Gieten, 8e in Steenwijk en 11e in de Profronde van Surhuisterveen. In 1996 won hij in het shirt van Olympia drie wedstrijd, de Ronde van de Drait te Drachten, Nieuw-Roden en Annen. Teuben, die inmiddels een baan bij Koga Miyata in Heerenveen had gevonden, was een toonbeeld van regelmaat. Gedurende het seizoen 1997 reed de weer naar zijn oude woonplaats teruggekeerde wielerfanaat voor de sponsorforamtie Tegeltoko uit Volendam, won vier criteriums en daarna keerde hij andermaal terug naar Olympia.