Ujfalušis loopbaan in het betaald voetbal begon bij Sigma Olomouc. De toen negentienjarige verdediger speelde er van 1997 tot en met 2000 honderd competitiewedstrijden, voor hij verkaste naar Hamburger SV.
Bij de Hamburger Sport Verein speelde de fysiek ingestelde verdediger 105 duels in het eerste, waarin hij twee keer scoorde. Beide goals maakte hij in het seizoen 2002/03. Dit was het eerste en enige seizoen dat hij boven de 30 competitiewedstrijden kwam bij HSV. Hij speelde bij de Noord-Duitse club samen met onder andere Nico-Jan Hoogma.
Ujfalušis spel bij Hamburger SV wekte de interesse van Fiorentina. Zijn tijd bij de Florentijnen duurde vier jaar en wederom meer dan honderd competitiewedstrijden. De Tsjech maakte in de 123 wedstrijden voor La Viola twee doelpunten. Bij Atlético Madrid kwam Ujfaluši vervolgens in zijn vierde verschillende nationale competitie terecht. Hij won een jaar later als basisspeler de UEFA Europa League 2009/10 met de club. Van 2011 tot 2013 speelde hij voor Galatasaray SK. In december 2013 beëindigde hij wegens aanhoudende blessures zijn loopbaan bij Sparta Praag.
De interlandcarrière van Ujfaluši begon in zijn periode bij Hamburger SV. Van 2001 tot en met 2009 speelde hij 78 wedstrijden voor het Tsjechische nationale team, waarin hij twee keer scoorde. In april van 2009 kwam er een einde aan zijn interlandloopbaan. Nadat Ujfaluši met enkele medespelers en verschillende prostituees was gezien in een restaurant op de avond na het verlies tegen zijn voormalige landgenoten uit Slowakije, had hij er geen zin meer in[1]. Met het nationale team speelde hij op het EK 2004, het WK 2006 en het EK 2008. Op het EK 2004 reikte hij met Tsjechië tot de halve finales, waarin de latere kampioen Griekenland te sterk was.
Hamburger SV
Atlético Madrid
