The Romanian champions ground out their third draw in five games to put a serious dent in the Bundesliga outfit's ambitions of reaching the knockout phase.
The result, combined with Chelsea's 1-0 defeat in Basel, means Schalke go into its final Group E fixture at home to the Swiss champions needing a win progress to the knockout stages.
In a game of few chances, the closest the hosts came was when Christian Tanase struck the woodwork with a late free kick, while the visitors had a goal disallowed 10 minutes before the break when Christian Fuchs tapped home, only to see the goal chalked off after the officials ruled the ball had previously gone out of play.
Steaua's defeat, which eliminates it from the competition, also means it equalled an unwanted Champions League record of 22 matches without a win, matching a low mark set by Spartak Moscow.
The hosts made three changes from its 1-1 draw in the league on Saturday, while Schalke made five alterations, including goalkeeper Ralf Fahrmann making his competition debut in place of Timo Hildebrand (hip). Julian Draxler (flu) was only fit enough for the bench.
In a quiet first half, Schalke was the first to threaten in the 18th minute when Ciprian Tatarusanu held Dennis Aogo's close-range effort after the ball had ricocheted around the Steaua box.
Steaua’s response was immediate, though, as Federico Piovaccari lobbed his effort over the bar from 25 yards after being played in by Alexandru Bourceanu.
Piovaccari then went even closer on the half-hour mark, with his acrobatic effort from eight yards out beaten away by Fahrmann after the striker had got on the end of Lukasz Szukala's knock down.
The visitors thought they had broken the deadlock a minute later when Fuchs tapped home Jefferson Farfan's cutback, but the Peruvian was adjudged to have let the ball roll out of play as he reached the byline.
Both sides went close from set pieces midway through the second half, as Fahrmann tipped Szukala's header over the bar before Jermaine Jones flashed a header wide of the post from Aogo's left-wing corner.
Tanase almost won it for the home side with 14 minutes remaining, his curling 25-yard free-kick shaving the outside of the post before Adam Szalai's flicked header four minutes later went narrowly wide at the other end.
The last chance of the game fell to Piovaccari, but the striker headed straight at Fahrmann from 10 yards out though he was totally unmarked.