The Bavarians had won all nine of their games this season, but saw their 100 per cent record shattered by the hosts, who made it two wins from two in their European campaign
The Bavarians dominated the match for long periods, but fell behind to an Alexander Pavlov strike. The visitors laid siege to the Belarusian goal for much of the rest of the match, but were left frustrated and were killed off by a dramatic Vitali Rodionov effort in the final stages.
Bayern would have been expected to take control of the match from the early stages, but backed by their passionate fans, it was BATE who made the early running.
Denis Polyakov was looking eager to push forward, and on one customary surge, found Rodionov, who forced a decent save from Manuel Neuer, who saw the effort late.
However, the Bavarians soon began to take control. Toni Kroos nicked possession from the lax Dmitri Likhtarovich, left goalkeeper Andrey Gorbunov in his wake, but, slightly off balance, could only send a shot against the woodwork.
Holger Badstuber attempted to break the deadlock with a 35-yard free kick, but bent the ball straight into Gorbunov's arms, before the keeper was quick off his line to claim it at Franck Ribery's feet.
The Bavarians thought that they had finally broken the deadlock on the 20-minute mark. Kroos picked up possession of the loose ball in midfield, threaded it through for Muller who tapped it across to Mandzukic to tap into the empty net, only to see their goal ruled out for an offside flag against the Germany international.
It was turning into one of those nights for Bayern and soon enough they were behind. Polyakov picked out Aleksandr Volodko, who played the ball into Pavlov's path, and the 28-year-old swept it home.
The visitors, riled up by falling behind, returned with new vigour, and within seconds they were almost level. Ribery weaved a path down the left, crossed it for Muller, whose header was acrobatically clawed behind by Gorbunov.
The resulting corner made its way to Lahm, who managed to pick out Mandzukic in the area, but the Croatian's header was not directed well, and Gorbunov was able make an easy save.
The captain was at the fore again as Bayern created one final chance of the first half to equalise, sending in a low cross to Mandzukic, who failed to control the ball. It almost broke to Muller, but the 23-year-old could not get the ball out of his feet before a challenge came in.
Within seconds of the restart, Mandzukic found himself in space, but could not manage to thread a ball through to Ribery, and Volodko signalled BATE's intent with an ambitious effort which sailed high over the bar.
A Kroos corner narrowly evaded the head of Dante, and, collecting the loose ball, Muller saw a vicious effort promptly charged down.
The hosts were dropping further and further back in an effort to quell the constant Bayern attacks and, as the visitors poured bodies forward, they left themselves susceptible to counterattacks.
On one occasion some masterful play from Aliaksandr Hleb, who had previously been quiet all night, played in Edgar Olekhnovich, who forced a superb save from Neuer with a ferocious right-footed strike from the edge of the area.
The former Barcelona man also played in Rodionov, who left Dante in his wake with a superb first touch, but skewed his shot wide when he should have tested Neuer at the very least. Hleb then presented Pavlov with an easy opportunity to double the score, only for the midfielder to sky his shot.
Time was running out for the Germans to turn it around, and their attacks were becoming increasingly frantic. A Kroos free kick was cleared as far as Shaqiri, who miscued a strike wide with his weaker right foot, before the Swiss youngster failed to take a Mandzukic knock-down under his control.
With 12 minutes remaining, any chances of a revival were dealt a critical blow. Hleb was the architect once more, playing in Rodionov, who played a slick one-two with Olekhnovich, before slamming the ball past Neuer.
Once again, Bayern advanced. Shaqiri tried to play in Muller, who couldn't control the ball, which broke to Claudio Pizarro, but the Peruvian's shot was stopped on the line by Gorbunov. Seconds later a corner broke to Ribery, who darted into the box before sending a left-footed effort crashing onto the bar.
They finally managed to pull one back in stoppage time when Ribery superbly tucked home Shaqiri's through ball, but it was too little too late. And as they frantically searched for an equaliser, they went further behind.
Dmitri Mozolevski surged forward down the left and squared the ball to Renan Bressan, who tucked it home to seal a famous victory for BATE.