Substitute Nacho Novo's 89th minute winner gave Rangers a priceless lead after the first leg of their Champions League third round qualifier.
Novo collected Lee McCulloch's headed flick-on and fired home a left foot shot from inside the 18-yard box.
Both sides chose to play with one up front and it contributed to a game of few chances - much to the anxiety of the Ibrox fans.
The game looked destined to end in a goalless draw until Novo's strike.
Kris Boyd dropped to the bench as Rangers boss Walter Smith changed his formation.
Brahim Hemdani came in as Rangers switched from a four to a five-man midfield, as the Ibrox club sought an advantage for the second leg in Belgrade.
The former Marseille skipper stepped in alongside Barry Ferguson and Kevin Thomson while Jean-Claude Darcheville continued up front, with Lee McCulloch and DaMarcus Beasley charged with providing crosses from the flanks.
Kirk Broadfoot replaced the injured Sasa Papac at left-back, while Steven Whittaker was on the bench for the first time since his £2m move from Hibernian.
MY SPORT: DEBATE
Broadfoot looked nervy in the opening minutes as a number of his passes failed to find team-mates.
Darcheville embarked on a lung-bursting run after five minutes and his shot was deflected for a corner, which Rangers failed to convert.
The visitors appeared happy to retain possession in the opening 15 minutes, but failed to create any chances despite retaining the ball for long spells.
Joao Lucas and Segundo Castillo knocked the ball around in central midfield to allow Red Star to settle into the game.
Red Star captain Ognjen Koroman looked dangerous going forward but his inability to tackle eventually earned him a booking - one of seven on the night for the visitors.
Rangers fans were unhappy with the assistant referee when he flagged Darcheville offside as he sped towards goal after collecting Ferguson's neat pass.
Castillo then sent an ambitious 35-yard shot high and wide in the first attempt on goal by Red Star.
The visitors almost took the lead in the 39th minute when Cuellar missed the ball as he attempted to head clear and Dordevic's first-time volley flew inches over the bar.
But both sides struggled to create chances with a congested midfield offering little in the way of creativity.
Rangers introduced Novo and Daniel Cousin for Beasley and Darcheville in an attempt to find a cutting edge in front of goal.
McGregor flapped at a cross with 20 minutes to go, but collected before any of the Red Star forwards could profit.
Cousin then went close with a rasping drive from 25 yards which just cleared the crossbar.
The final 15 minutes was untidy, with Red Star players happy to either contain or foul Rangers players.
Ferguson could have broken the deadlock in 85 minutes, but his shot from a tight angle hit the side netting, with Novo unmarked inside the box.
But the Spaniard would be rewarded with a minute remaining when he scored the winner.
Rangers: McGregor, Hutton, Cuellar, Weir, Broadfoot, McCulloch, Ferguson, Hemdani, Thomson Beasley, Darcheville. Subs: Carroll, Boyd, Novo, Adam, Murray, Whittaker, Cousin
Red Star Belgrade: Randjelovic, Bronowicki, Gueye, Tutoric, Andjelkovic, Koroman, Castillo, Lucas Milijas, Raskovic, Dordevic. Subs: Radivojevic,Pantic, Barcos,Bajalica, Molina, Salas, Milovanovic
Referee: Martin Hansson
Att: 35,364
~RS~q~RS~~RS~z~RS~36~RS~)