Ulihrach turned professional in 1993. He won his first top-level singles title in July 1995 at Prague, where he defeated Javier Sánchez in the final. His second followed three months later at Montevideo, where he beat Alberto Berasategui in the final.
In 1996, Ulihrach was part of the Czech Republic team which finished runners-up at the World Team Cup. In 1997, Ulihrach beat the then-World No. 1 Pete Sampras en route to his first hardcourt final at the Indian Wells Masters. He was defeated in the final by Michael Chang. Ulihrach reached a career-high singles ranking of World No. 22 in May 1997.