A Tisza parti Magyarkanizsán született, kereskedő apját eredetileg Kracsunnak hívták. Tolnai már gyerekként sokat olvasott, szabadidejében a bátyjától kapott ponyvaregényeket, idegenlégiós könyveket bújta. Írással a zentai magyar gimnázium tanulójaként kezdett foglalkozni, első kisprózáját A kavics címmel az újvidéki Ifjúság című hetilap közölte 1956-ban.
Érettségi után az újvidéki egyetem magyar szakán tanult, majd a zágrábi egyetemen folytatott filozófiai tanulmányokat. Verseket 1960-tól ír, lírai művei kezdettől fogva metrum, rím, központozás és rendszerint nagy kezdőbetűk nélküli szabadversek. Első verseskötete, a Homorú versek 1963-ban jelent meg.
1961-ben lett az Ifjúság című hetilap Symposion elnevezésű művészeti mellékletének szerkesztője, majd az ebből létrejövő, 1964-ben induló Új Symposion alapító munkatársa. 1969 és 1974 között a folyóirat főszerkesztője volt, de a jugoszláv cenzúra nyomására távozott. 1974 és 1994 között az újvidéki rádió magyar adásának szerkesztője és képzőművészeti kritikusa volt. Később, 1992-től 2004-ig a Veszprémben megalakult Ex Symposion főszerkesztője volt, azóta is a lap munkatársa. 1966-tól 1990-ig a Jugoszláv Írószövetség tagja, majd utolsó elnöke volt, 1990-től a Magyar Írószövetség tagja.
A hatvanas évek elejétől Újvidéken élt, ahol barátaival, Végel Lászlóval és Domonkos Istvánnal a helyi irodalmi élet prominens alakjaivá váltak. Domonkossal közös verseskötetet is publikáltak 1968-ban Valóban mi lesz velünk címmel. Tolnai az újvidéki Forum Könyvkiadó 1968. évi regénypályázatára írta meg első regényét, Rovarház címmel, és bár a mű díjat nem kapott, formai újításaival, avantgárd kísérletező jellegével mégis fontos mérföldköve lett a magyar prózairodalomnak. Ezt követően szinte évente jelentkezett verseskötettel, illetve prózai munkával, műveit kezdetben az újvidéki Forum jelentette meg a Symposion könyvek sorozatban. 1983-ban a Magvető Kiadó adta ki válogatott verseinek gyűjteményét Vidéki Orfeusz címmel, a kötet a költemények mellett tartalmazza szlovéniai útinaplóját (Az uralkodó csúcs), valamint A zsilett kora című ciklusban részleteket kisprózakötetéből, a Virág utca 3-ból is. A kritika által nagyon kedvezően fogadott műben Tolnai magánmitológiájának jellegzetes motívumai (a gyermekkor helyszíne, a vidéki kisváros emberei, történetei) jelennek meg. A motívumok közt szerepel a falu bolondja Wilhelm alakja, akinek egy egész, szintén nagy sikerű kötetet szentelt Wilhelm-dalok avagy a vidéki orfeusz címmel.
A versek, prózák mellett írt a színpadi formát és nyelvezetet megújító drámákat is. A Bayer aspirin című monodrámát először 1981-ben az Újvidéki Színházban láthatta a közönség Jancsó Miklós rendezésében és Ladik Katalin előadásában, majd 2009-ben a Budapest Bábszínház is műsorára tűzte, Végeladás című darabját a kecskeméti Katona József Színház vitte színre.
Tolnai Ottó pályájának kiemelkedő műve a Költő disznózsírból című kötet, amely 2005-ben megkapta a Magyar Irodalmi Díjat. A mű az 1998 márciusában Parti Nagy Lajossal folytatott hatnapos életútinterjú átdolgozásából készült, kritikusai szerint egyenesen Tolnai Ottó művészetének a középpontjába kalauzolja az olvasót. 2016-tól a Jelenkor Kiadó gondozásában jelenik meg életműsorozata, amelynek első darabja a Világpor című kötet volt. A sorozat legutóbbi darabja, a 2018-as év egyik irodalmi szenzációja a Szeméremékszerek. A két steril pohár című kötete volt, amely a Szabadka melletti fürdővárosban, Palicson játszódik, ott, ahol 1994 óta Tolnai Ottó is él.
Pályájáról, művészetéről 1994-ben jelent meg Thomka Beáta monográfiája, 2005-ben pedig Mikola Gyöngyi „A Nagy Konstelláció. Kommentárok Tolnai Ottó poétikájához” című munkája.
Tolnai Ottó munkásságáért számos rangos elismerést kapott. 1967-ben és 1980-ban Híd-díjjal tüntették ki, 1981-ben József Attila-, 1993-ban Ady Endre-, 1999-ben Weöres Sándor-díjat kapott, 2000-ben A Köztársasági Elnök Aranyérmével, valamint Radnóti Miklós-díjjal ismerték el. 2007-ben megkapta a Kossuth-díjat az avantgárd hagyomány magas szintű megújításáért és a vajdasági magyar irodalom szervezésében vállalt szerepéért. 2009-ben a Grenadírmars című kötetéért Artisjus irodalmi nagydíjjal tüntették ki. 2017-ben megkapta a Vajdasági Írók Egyesületének életműdíját, 2018-ban a Hazám-díjat.
1998-tól a Széchenyi Irodalmi és Művészeti Akadémia tiszteletbeli tagja. 2001 júniusában a Digitális Irodalmi Akadémia tagjai sorába választották.
