Na zijn studie heeft Tarjan een uitgebreide loopbaan gehad, zowel in academische als in commerciële kringen. Hij heeft gewerkt aan de Cornell University te New York, het California Institute of Technology ofwel Caltech en tussen 1974 en 1980 was hij docent in Stanford. Daarna werkte hij gelijktijdig aan het AT&T Bell Laboratories en de New York University. In 1985 keerde hij als hoogleraar terug naar Princeton, waar hij nog steeds werkt (hij bekleedt de leerstoel van de James S. McDonnell Distinguished University Professor of Computer Science). Tegelijkertijd met zijn werk voor Princeton heeft hij gewerkt bij NEC, MIT, InterTrust, Compaq en Hewlett-Packard (ook hier werkt hij nu nog).
Tarjan heeft twee boeken gepubliceerd en 55 artikelen en conferentiestukken gepubliceerd. Hij heeft ook zo'n 155 publicaties beoordeeld voor officiële publicaties. Daarnaast heeft hij zich als redacteur, lid of referee verdienstelijk gemaakt voor 26 organisaties binnen de Association for Computing Machinery.
Tarjan is tijdens zijn loopbaan geëerd met zo'n 20 prijzen en fellowships. Een hiervan was de Turing Award van 1986, die hij samen met John Hopcroft won voor fundamentele resultaten in het ontwerp en de analyse van algoritmen en datastructuren.
