The German visitors were the better side on the night and were good value for their victory, as they ended their opponents' long-standing unbeaten home run which stood at 21 games in all competitions.
Failure to win for the Hoops, or indeed claim a point, means that they are bottom of the Group C standings midway through and now left clinging onto hope of ousting Gladbach for a place in the Europa League.
Celtic were looking incredibly open at the back right from the off, with the visitors spraying a few shots wide of the target inside the opening quarter of the match.
The first real shot on target arrived 17 minutes into the match when Ibrahima Traore looked to pick out the bottom corner with a curled effort, which Craig Gordon got across well to keep out before latching straight on to the loose ball.
Jonas Hoffmann was the next to test Gordon, this time from closer range after more gaps appeared in the Celtic defence, but the German midfielder came out second best in his battle with the Bhoys' stopper.
One of four players to be restored from the weekend win over Motherwell, Israel international Nir Bitton, was particularly struggling at times in the first half as he gave away possession for the lively Andre Hahn to blast away attempt number three on target.
Despite being without arguably their three most important players due to injury, which forced boss Andre Schubert into abandoning his three-at-the-back system in favour of a flat-back four, it was Gladbach who were continuing to control the game as half time approached.
However, Celtic did create the best attacking move of the half right on the brink of the interval when Tom Rogic - one of those rested last time out - carved open the opposition defence with an intricate through-ball.
Scott Sinclair timed his run well to get on the end of the ball, though he failed to keep his attempt down with only Yann Sommer to beat as the sides went into the break all square - a scoreline that suited neither side.
The Hoops did come out for the second half with far more urgency to their game but, a wayward Sinclair header aside, the possession did not amount to any tangible chances in front of goal.
That proved to be costly as, with just short of an hour played, the game's best outfield player edged his side ahead following a Kolo Toure error, putting them on their way to a first away win in the European Cup proper since 1977 when they made it to the final.
Toure was unable to usher the ball out of play which allowed Hahn to wrap his boot around it and find Lars Stindl, who fired past Gordon before he could fully set himself for a shot he was perhaps not expecting.
It was a case of Celtic pushing for a leveller from that point on, but the second period was proving to be devoid of any real chances after that key Stindl strike.
The second shot of any note did not arrive until 13 minutes from time, in fact, as another Toure error allowed Borussia to pounce and Hahn to smash the ball past Gordon for a second goal.
A stunned Celtic Park watched on for the remainder, as their side saw their poor run against German opposition continue - now just the one win in 11 meetings in European competition, the latest of which is a killer blow to their last-16 hopes.