Naby Keita's stunning strike in the second minute of the game put the visitor's in front but Florian Neiderlechner equalised for the hosts after a quarter of an hour.
Timo Werner then took centre stage for the remainder of the half as he scored a brace of goals to send the visitors into halftime with a commanading lead.
Marcel Sabitzer added a fourth late on to seal yet another win for Die Roten to send the visitor's six points clear at the top of the table.
Both teams scored early
The visitors started the game on the front foot and went in front within two minutes of the game starting. Keita scored from fully 30 yards outside the box as his shot arrowed into the top corner of the net.
The goal seemed to shellshock the hosts until a great cross into the box from Pascal Stenzel found Niederlechner at the back and the striker saw his shot somehow find its way into the net past the goalkeeper.
Apart from the goal though it was a really one-sided half as the visitors got themselves back in front for the second time in the match.
Werner at the double for the visitors
A through ball from Diego Demme found Werner, who sneaked the ball into the net past Alexander Schwolow, who should have done better, to give the visitors what they deserved.
Things got even better for the league leaders when a lovely free-flowing move ended with Werner scoring his second of the game. Emil Forsberg was the man to produce the wonderful through pass to the striker, who curled the ball past the helpless Schwolow, to really put the visitors in the driving seat.
It was the extensive pressing that really caused the hosts to make a number of mistakes through the half and with the confidence flowing through their veins, the visitors didn't let them go unpunished as it was turning out to be another fantastic night for the high-flying leaders.
Even second half
The second half was much more even between the sides as the visitors kept a strong base at the back to stop the hosts from getting back into the game.
The hosts though did create the first big chance of the second half when from a corner kick, Nicolas Höfler hit the crossbar from close range.
The visitors also went close to adding a fourth when a lovely through pass from Forsberg played Sabitzer in on goal but a heavy touch from the winger made the chance difficult as he could only turn the ball onto the post.
Sabitzer added a fourth late on for the visitors
Sabitzer though did add a fourth goal not long after as again Forsberg played the ball through to him and the Austrian drilled the ball into the bottom corner of the net past the helpless Schwolow, who got a hand to the ball.
After the fourth goal, it was like a training session for the visitors as they kept the ball at will and stopped the hosts from even getting a second goal on the night.
The game therefore ended with the visitors winning their seventh game in a row to maintain their unbeaten start to the season.