Начинал играть в «Динамо» (Тбилиси). В 1986 году в составе сборной Грузинской ССР выиграл всесоюзный турнир «Кубок Надежды» (под фамилией Осипов)[6]. В «Динамо» в то время должны были играть футболисты только под грузинской фамилией, и отец Омари, Михаил Осипов[7], решил, чтобы сын взял фамилию бабушки — Тетрадзе[5][8].
Затем играл в «Динамо» (Москва) и «Алании».
1 февраля 1993 сломал челюсть в результате избиения сотрудниками милиции[9].
В 1995 году после ухода из «Динамо» (Москва) на Кубке Содружества 1995 года выступал за московский «Спартак», однако после турнира подписал контракт с «Аланией». В 1997 году заключил контракт с итальянским клубом «Рома» (Рим). Однако карьере в Италии помешала тяжёлая травма (сильное растяжение крестообразной связки колена), полученная в матче сборной против Люксембурга 30 апреля 1997 года. 2 февраля 1999 года расторг контракт с «Ромой» и вернулся в Москву. Пройдя сборы перед сезоном 2000/01 с «Удинезе», Тетрадзе принял предложение греческого ПАОК, с которым выиграл Кубок Греции-2001. Из-за желания снова попасть в сборную России вернулся в «Аланию».
За сборную СНГ/России провёл 40 матчей, забил 1 гол. Также за сборную России сыграл в 1 неофициальном матче (забил 1 гол). Участник чемпионата мира 1994 года (1 матч), чемпионата Европы 1996 года (3 матча, 1 гол). За олимпийскую сборную СССР сыграл 5 матчей, выступал за юношескую сборную СССР. Был в списке кандидатов на поездку на чемпионат мира по футболу 2002 года, но не попал в итоговую заявку[10][11][12], так как не смог убедить тренеров сборной в своей необходимости[13].
В 2006 году — тренер клуба «Крылья Советов». В том же году, по словам Сержа Бранко, Тетрадзе, являвший ассистентом главного тренера, угрожал футболисту пистолетом за отказ игрока добровольно проиграть матч клубу «Москва»[14]. С 2007 года работал главным тренером «Анжи». 16 марта 2010 года Тетрадзе подал в отставку с поста главного тренера «Анжи»[15]. По мнению спортивного обозревателя «Новой газеты», Тетрадзе подал в отставку из-за нежелания участвовать в «договорных матчах» своей команды с клубами из соседних регионов, «Спартаком-Нальчиком», «Тереком» и «Аланией»[16][17]. Официальными причинами отставки стала усталость и желание быть с семьёй; в то же время Тетрадзе не опроверг и существование других причин, хотя и отмёл предположение о том, что к отставке привели договорные матчи[5]. 8 мая 2010 года возглавил нижегородскую «Волгу»[18]. В том же году Александр Тарханов сказал, что якобы кто-то из руководства «Волги» обращался к возглавляемым им «Химкам» о «сдаче» матча. Тетрадзе на это ответил, что ему неприятно слышать такое и что команда улучшила своё турнирное положение только за счёт игры[19]. В 2011 году Омари опроверг слухи о договорном матче его команды и клуба «Анжи»[20]. 15 июня 2011 года недовольный результатами команды президент «Волги» Алексей Гойхман отправил Тетрадзе в отставку[21].
В феврале 2013 года встал у руля казахстанского клуба «Жетысу»[22]. В июле 2014 года клуб начал испытывать финансовые проблемы и подал в суд на Тетрадзе[23], и в сентябре 2014 Омари вместе со своим штабом покинули команду по взаимной договоренности сторон[24], в том числе из-за инцидента с задержанием одного из помощников тренера нарядом милиции[25].
7 октября 2015 года назначен тренером ФК «Енисей»[26]. По окончании сезона подал в отставку, хотя формально не тренировал команду последние несколько туров.
30 мая 2016 года подписал контракт на полтора года с казахстанским ФК «Тобол»[27], но уже через год был отправлен в отставку[28].