Peter Odemwingie scored the only goal to give Nigeria a victory that means World Cup debutants Bosnia-Hercegovina will not progress from Group F.
The Stoke forward struck in the first half to give Nigeria their first win at a World Cup finals since 1998.
The goal came just seven minutes after Bosnia striker Edin Dzeko had a goal incorrectly disallowed for offside.
Nigeria will reach the knockout stages if they get a point against Argentina, or if Iran fail to beat Bosnia.
Odemwingie's decisive strike came just a month after he returned to the Nigeria squad following a two-year absence caused by adispute with coach Stephen Keshi.
Knowing they needed a win to stay in their first World Cup finals, Bosnia attacked from the start but were vulnerable in defence, with Odemwingie, John Mikel Obi and Michael Babatunde all squandering early chances for Nigeria.
Bosnia briefly thought they had taken the lead when Dzeko latched onto a pass from Miralem Pjanic, but the Manchester City forward was denied by an offside flag, though replays suggested he had timed his run well.
The Super Eagles made the most of the let-off as Emmanuel Emenike powered past Emir Spahic on the right before finding Odemwingie, who shot through the legs of his Stoke team-mate Asmir Begovic to score.
Pjanic stood out with a string of perceptive passes, but Dzeko in particular could not capitalise on the Roma midfielder's fine work, spurning more opportunities before half-time.
Nigeria absorbed Bosnian pressure early in the second half, but they counter attacked effectively and came close to going further ahead when Babatunde and Emenike forced saves from Begovic in quick succession.
Bosnia continued to press, but substitute Vedad Ibisevic, who came off the bench to score in the defeat by Argentina, wasted a chance to equalise when he bundled a cross wide despite finding space in the area.
And, with seconds of injury time remaining, Dzeko scuffed a shot which Nigeria goalkeeper Vincent Enyeama deflected onto the post and away to safety.
Nigeria striker Peter Odemwingie: "It's been 16 years with no victory for our fans. We had to work hard for this - they are a quality team.
"We are happy to bounce back after what people thought was a poor performance in the first game. It was very important to win.
"From now on we're looking upwards. Hopefully these three points will get us through to the second round."
Bosnia-Hercegovina coach Safet Susic: "I don't have any recriminations. They are all depressed, disappointed, silent.
"They surprised us with their speed and movement. They wanted to win probably that much more than us.
"I was told there was no offside. But this is not the first or last refereeing mistake, not just at the World Cup or elsewhere."