Europa

2002 rückte Teletović als 17-Jähriger in die erste Mannschaft von KK Sloboda Dita aus Tuzla auf, die in Bosnien und Herzegowina zwischen 1994 und 2002 in jedem Jahr das Finale um die Meisterschaft im bosnischen Landesteil erreicht hatten und auch fünfmal siegreich waren neben sechs nationalen Pokalsiegen. Bereits 2004 wechselte er ins Ausland und spielte in Belgien für den zuvor zehnfachen belgischen Meister BC Ostende. Mit dem unter dem Sponsorennamen Telindus antretenden Verein gewann er in seiner zweiten Spielzeit 2006 zusammen mit unter anderem seinem Landsmann Elvir Ovčina und dem deutschen Nationalspieler Denis Wucherer eine weitere Meisterschaft. Anschließend wechselte er in die spielstärkere spanische Liga ACB.

Der spanische Vizemeister TAU Cerámica, so der damalige Sponsorenname von Saski Baskonia, nahm ihn für die Spielzeit 2006/07 unter Vertrag. In der EuroLeague 2006/07 marschierte man mit nur zwei Vorrundenniederlagen bis ins Halbfinale, wo man dem späteren Titelträger Panathinaikos Athen unterlag. In der EuroLeague 2007/08 unterlag man im Halbfinale dem Vorjahresfinalisten und späteren Titelträger PBK ZSKA Moskau. Dafür gewann man die spanische Meisterschaft 2008 gegen FC Barcelona, gegen die man in der Vorsaison noch in der Halbfinalserie der Meisterschaft ausgeschieden war. Teletović selbst wurde als Most Improved Player (meistverbesserter Spieler) der spanischen Meisterschaft in dieser Spielzeit ausgezeichnet.

In der Spielzeit 2008/09 verlor man als Titelverteidiger und Erstplatzierter der regulären Spielzeit die Finalserie gegen FC Barcelona, ebenso die Viertelfinalserie in der EuroLeague 2008/09, die Barcelona im Anschluss gewinnen konnte. Das Halbfinale im spanischen Pokalwettbewerb Copa del Rey gewann man den katalanischen Verein, nach dem Titelgewinn in diesem Wettbewerb wurde Teletović zum MVP des Pokalturniers ernannt.

In der EuroLeague hatte er in 21 Spielen mit einem Punktedurchschnitt von 13 Punkten pro Spiel 121 Wurfversuche aus der Distanz von hinter der Dreipunktelinie mit einer guten Erfolgsquote von 42,1 %, bei den Würfen aus der Nah- und Mitteldistanz hatte er 66 Versuche, die er aber mit einer überragenden Erfolgsquote von 74,2 % abschloss, was den Bestwert der damaligen Euroleague-Saison darstellte und seine gute Wurfauswahl unterstrich. Die Erfolgsquote aus der Nah- und Mitteldistanz war nahezu gleich hoch wie seine Freiwurfquote.

In der Spielzeit 2009/10 trat man unter dem neuen Sponsorennamen Caja Laboral an und schied in der EuroLeague 2009/10 wie in der Vorsaison im Viertelfinale aus, diesmal gegen ZSKA Moskau, nachdem man sich in der Zwischenrunde nur äußerst knapp gegenüber dem anderen russischen Vertreter BK Chimki behaupten konnte, gegen die man im direkten Vergleich punktgleich war. Teletović glänzte in den letzten drei Zwischenrundenspielen mit jeweils dem mannschaftsinternen Bestwert von 25 Punkten. In der spanischen Meisterschaft wurde er am sechsten Spieltag erstmals zum MVP des Spieltags gewählt.

Am Ende der Hauptrunde belegte man hinter FC Barcelona, die erneut die EuroLeague gewannen, den zweiten Platz. In der Finalserie der Meisterschaft trafen die beiden Kontrahenten zum dritten Mal in Folge aufeinander und Caja Laboral behielt in drei Spielen knapp jeweils das siegreiche Ende für sich, davon zwei Siege mit nur einem Punkt Unterschied.

In der Spielzeit 2010/11 traf man bereits in der Halbfinalserie der Meisterschaft aufeinander, die diesmal der spätere Titelträger FC Barcelona in drei Spielen deutlich mit mindestens zehn Punkten Unterschied pro Spiel gewinnen konnte. In der EuroLeague 2010/11 schied man erneut im Viertelfinale gegen den späteren Finalisten Maccabi Tel Aviv aus.

NBA

Zur Saison 2012/13 wechselte Teletović in die NBA zu den Brooklyn Nets. In seiner ersten Saison kam er in 53 Spielen zum Einsatz. Hierbei konnte er im Schnitt 3,5 Punkte und 1,8 Rebounds erzielen. Im Laufe der Saison 2013/14 konnte er bei durchschnittlich 19 Minuten seinen Punkteschnitt auf 9,1 Punkte steigern. Am 24. Januar 2014 erzielte er seinen Karrierebestwert von 34 Punkten in der Heimpartie gegen die Dallas Mavericks. Dabei traf er unter anderem sieben von elf versuchten Dreipunktwürfen.

Im Januar 2015 wurde beim kurzatmigen Teletović eine beidseitige Lungenembolie diagnostiziert. Die lebensgefährliche Erkrankung konnte erfolgreich behandelt werden und Teletović kehrte bereits nach knapp drei Monaten noch vor Saisonende auf das Spielfeld zurück. Die Nets machten Teletović zunächst auch ein offizielles Angebot zur Vertragsverlängerung, was sie jedoch nach drei Wochen zu Beginn des Transferfensters zurückzogen.

Eine Woche später unterschrieb Teletović für die NBA 2015/16 einen Einjahresvertrag bei den Phoenix Suns. Teletovic stellte am 5. April 2016 den NBA-Rekord von Chuck Person aus der Saison 1994–95 ein, als er mehr als 164 Dreipunktwürfe in der Saison als Bankspieler traf.

Am 8. Juli 2016 unterschrieb er einen Vertrag bei den Milwaukee Bucks, nachdem sein einjähriger Vertrag auslief und weder er noch die Suns die vertraglich festgelegte Option zog.

Im Spieljahr 2017/18 verpasste er aufgrund einer Knieverletzung 16 Begegnungen in Folge und musste operiert werden, im Dezember 2017 wurde zudem eine Lungenembolie festgestellt. Ende September 2018 gab er aus gesundheitlichen Gründen das Ende seiner Leistungssportkarriere bekannt und wurde Vorsitzender des bosnischen Basketballverbandes. Teletović bestritt insgesamt 343 Spiele in der NBA.