Belodedici won 55 caps with Romania, representing the nation at the 1994 World Cup and two European Championships.
Belodedici was born in a family of Serbian ethnicity in the village of Socol, near the border with Serbia. He began playing organized football at the late age of 16.
Belodedici spoke only Serbian until elementary school, and completed his first four grades in that language. In the fifth he began learning Romanian, which he eventually mastered with the help from his Romanian junior national team team-mates Gavril Balint and Gheorghe Hagi. He joined the youth squad of Minerul Moldova Nouă in 1978, aged 14, his first coach being Olimp Mateescu; three years later he moved to Luceafărul București, a team created by the Romanian Football Federation for the purpose of gathering all talented young players in the country in one squad.
In the summer of 1982, Belodedici was signed by FC Steaua Bucureşti, being selected by the club's chairman Ion Alecsandrescu, who was in search for a high quality sweeper. He finished his first season with 17 Liga I appearances, then proceeded to become a first-team regular in the following seasons as the club won five consecutive national championships, including two doubles.
Belodedici helped Steaua become the first Romanian – and Eastern Europe – club to win the European Cup in 1985–86, playing the full 120 minutes in the final against FC Barcelona in Seville. He also started in the subsequent UEFA Super Cup, won against FC Dynamo Kyiv.
In 1988, when Nicolae Ceauşescu was still in power, Belodedici defected from his home country to the neighbouring Socialist Federal Republic of Yugoslavia. He later gave an account of his escape to Belgrade: once he saw himself in the city, he contacted the president of Red Star Belgrade, but could not get through due to widespread commotion in the team over their defeat in the derby with FK Partizan. A Serbian friend attempted to have him agree to sign for Partizan instead, but the player insisted that he would only play for Red Star; the president interrupted their conversation and, when he realized that he was in fact the 1986 European Cup winner, he immediately signed him.
However, during his first year, Belodedici had to play without a legal contract, and only in friendly matches, as the Romanian authorities forged his professional player contract, and UEFA suspended him for one year on the basis of data furnished. The Ceaușescu regime found him guilty of treason and sentenced him to ten years of prison in absentia; after the Romanian Revolution of 1989, all charges were dropped, and Belodedici returned to Bucharest.
In 1989, Belodedici was given the green light to play for Red Star and, soon after, became a permanent fixture on the squad. In 1990–91 he won the European Cup for the second time, scoring in the final against Olympique de Marseille during the penalty shootout, and became the first player to conquer the tournament with two different clubs, by playing in both finals; amongst other accolades, he also won three Yugoslav First League championships in a row.
Belodedici signed with Valencia CF for the 1992–93 season, being a starter in his second year as the Che finished in seventh position, with no fewer than four managers being used during the campaign, including Guus Hiddink twice.
In 1994 he moved to Real Valladolid, with the team ranking 19th but avoiding relegation as La Liga was expanded from 20 to 22 clubs. He spent his last season in Spain with Villarreal CF from Segunda División, in a return to the Valencian Community.
Belodedici spent two years in Mexico with Atlante FC. In 1998, aged 34, he returned to his main club Steaua, still being a relatively important defensive unit and winning two major titles, including the 2001 national championship.
Belodedici retired from football in June 2001, having appeared in 235 games in Romania's top flight (21 goals) and winning 11 major titles. Subsequently he worked with the Romanian Football Federation, coordinating national youth teams.
Belodedici made his debut for Romania on 31 July 1984 – aged 20 – in a 1–0 friendly win over China. During 1987 he scored three of his five international goals, one in the UEFA Euro 1988 qualifiers against Albania (5–1 win in Bucharest).
Because of his escape to Yugoslavia, Belodedici was excluded from the national team during more than three years. He returned in time to be selected and play all the games at the 1994 FIFA World Cup in the United States as they exited in the quarter-finals, missing his attempt in the shootout against Sweden in the last-eight stage; additionally, he was selected for the Euro 1996 and Euro 2000 tournaments, totalling four appearances combined and reaching the quarter-finals in the latter.Scores and results list Romania's goal tally first. "Score" column indicates the score after Belodedici's goal.
Liga I: 1984–85, 1985–86, 1986–87, 1987–88, 1988–89, 2000–01
Cupa României: 1984–85, 1986–87, 1987–88, 1988–89, 1998–99
European Cup: 1985–86
UEFA Super Cup: 1986
Yugoslav First League: 1989–90, 1990–91, 1991–92
Yugoslav Cup: 1989–90
European Cup: 1990–91
Intercontinental Cup: 1991