Die Entdeckungsgeschichte beginnt 1946, als die Sowjetisch-Mongolische Paläontologische Expedition unter Leitung von Ivan Yefremov in der Nemegt Formation der Ömnögovi-Provinz einen großen Theropoden-Schädel mit Unterkiefer und Halswirbeln barg (PIN 551-1). Zwischen 1948 und 1949 folgten drei weitere Skelette; ab 1948 nahm auch Evgeny Maleev an den Expeditionen teil. Maleev beschrieb das Material 1955 in zwei separaten Publikationen in Doklady Akademii Nauk SSSR: In der ersten (Band 104, Heft 4, S. 634–637) stellte er PIN 551-1 als Tyrannosaurus bataar vor. In der zweiten (Band 104, Heft 5, S. 779–783) beschrieb er drei weitere Taxa: Tarbosaurus efremovi (PIN 551-2, benannt nach Ivan Yefremov), Gorgosaurus lancinator (PIN 553-1) und Gorgosaurus novojilovi (PIN 552-2). Diese beiden Publikationen werden in der Literatur häufig vermischt – es ist wichtig zu wissen, dass T. bataar und T. efremovi in verschiedenen Artikeln beschrieben wurden.
1965 erkannte Anatoly Rozhdestvensky (Paleontologicheskii Zhurnal 1965(3):95–109), dass alle vier Maleev-Exemplare verschiedene Wachstumsstadien einer einzigen Art darstellten, und schuf die bis heute gültige Kombination Tarbosaurus bataar. Ab 1963 lieferten die Polnisch-Mongolischen Expeditionen unter Zofia Kielan-Jaworowska weiteres, umfangreiches Material.
Der wohl spektakulärste Aspekt der Tarbosaurus-Geschichte ist der Schmuggel-Fall von 2012. Am 20. Mai 2012 wurde ein nahezu vollständiges Skelett (ca. 2,4 m hoch, 7,3 m lang) bei Heritage Auctions in Manhattan für 1.052.500 Dollar versteigert – doch der Verkauf wurde nie abgeschlossen. Die mongolische Regierung erhob sofort Einspruch, und das US-Heimatschutzministerium (ICE/HSI) beschlagnahmte das Skelett. Es stellte sich heraus, dass der Fossiliensammler Eric Prokopi aus Gainesville, Florida, das Skelett illegal aus der Mongolei geschmuggelt und unter falschen Zollangaben eingeführt hatte. Prokopi bekannte sich im Dezember 2012 schuldig, kooperierte mit den Behörden und half, über 18 weitere geschmuggelte Dinosaurier-Fossilien sicherzustellen. Im Mai 2013 wurde das Tarbosaurus-Skelett an die Mongolei zurückgegeben und auf dem Sukhbaatar-Platz in Ulaanbaatar ausgestellt. Prokopi wurde am 3. Juni 2014 von Richter Hellerstein zu drei Monaten Haft, drei Monaten Halfway House und einem Jahr Bewährung verurteilt. Der Fall gilt als Wendepunkt im internationalen Kampf gegen den illegalen Fossilienhandel.