Regine Heitzer first competed in World and European Figure Skating Championships in 1958 when only aged 14. At the age of 16, in 1960, she won her first of seven consecutive Austrian single titles, bettering the record of Herma Planck-Szabo, who won six titles. Heitzer’s seven titles still stands as an Austrian record through 2013. In the same year she also won her first medal at the European Championships with silver and competed at the 1960 Olympics before finishing fourth at the 1960 World Championships. In the following years she won three more silvers (1961, 1962, 1964) and one bronze (1963) medal at the European Championships as well as three silver (1963-1965) and one bronze (1962) at the World Championships. All her silver medals came when Dutchwoman Sjoukje Dijkstra won gold, and this was also repeated at the 1964 Winter Olympics when Heitzer won silver behind Dijkstra in front of the home crowd. After Dijkstra turned professional in 1965 Heitzer won two European Championships titles in 1965 and 1966 before turning professional herself. From 1967 onwards Heitzer skated for Wiener Eisrevue and Holiday on Ice. In 1971 a knee surgery ended her career and her last appearance on ice was in 1979 when she skated with Emmerich Danzer to promote the World Championships held in Vienna.
After the end of her career in 1971 she started to work in the family business, an upholstery fabrics wholesaler in downtown Vienna. Heitzer later took over the company and converted it to a furniture store before she retired in 2010. In 1996 she was awarded a Decoration of Honour in Silver for Services to the Republic of Austria.