In 1992, she was the surprise winner of the Women's 100 m hurdles race at the Olympic Games in Barcelona, and she was voted the Best Balkan Athlete that same year.

This success made her the first Greek woman ever to reach a track final in the Olympic Games.

After her Olympic gold medal Patoulidou decided to switch back to the long jump, her first love, believing that she had achieved as much as possible in the 100 m hurdles.

In the 2000 Sydney Olympic Games, Patoulidou was a member of the 4 × 100 m relay team that reached the semi-finals and ended up in the 13th place.

She was also one of the penultimate runners of the 1996 torch relay in Atlanta, joining Evander Holyfield and Janet Evans.