And as if to give an indication of what's to come, his most notable action was to tell stars Luca Toni and Frank Ribery to quit messing around after a bit of practice pitch tomfoolery.
The message is clear: clown time is over.
Having won the league twice from 1989-1991 during a previous stint at Bayern's helm, Heynckes has been brought in to restore order, ensure Munich qualify for the Champions League and, if possible, engineer a last-minute fight-back to take the Bundesliga title.
A tall order with only four remaining weeks remaining in the season. And to fill it, Heynckes is going to need not only to institute a new post-Klinsmann culture, but to break a few negative streaks of his own.
So can he save Bayern? And if so how?
The tactical void under Klinsmann extended so far that once-mighty Bayern forgot basics such as spreading the field.
That meant they over-relied on the individual talents of Toni and Ribery. Opponents could double- and triple-team both stars, creating the sort of frustration that Ribery vented in getting himself sent off in last weekend's 1-nil, Klinsi-crushing loss to Schalke.
Expect Heynckes - a former striker who played for Moenchengladbach and the Bundesliga's all-time third-leading scorer - to put more offensive firepower on the pitch, probably going with two attacking forwards instead of one.
That would mean a second chance for Lukas Podolski, whom Klinsmann for some reason seemed determined to reduce to the role of apathetic reserve.
And it also probably entails the end of the line for the non-entities - Lell, Ottl and Sosa - whom Munich fielded in its home humiliation by Schalke.
The most immediate problem is that Ribery is suspended for one match after picking up that red card. Players like Hamit Altintop and above all Bastian Schweinsteiger are going to have to shoulder more of the immediate load.
But a big question - one that's the key to Bayern's late-season gamble - remains. Can Heynckes convince his new charges to get on with the program?
Heyncke's most recent results in the Bundesliga are nothing to write home about, and no one has ever accused him of being a master communicator.
Indeed, he got along so badly with a trio of stars at Frankfurt, which he coached from 1994 to 1995, that they went on strike, refusing to play at all.
Although he did win the Champions League with Real Madrid in 1998, he was fired after one season for getting poor results in the Spanish domestic league. The same was true with Heynckes and Schalke in 2004 - minus, of course, the Champions League title.
And returning to Gladbach for the 2006-7 campaign, Heynckes started the season with four victories, after which the team failed to win another game. Heynckes stepped down in January, and Gladbach were relegated.
Bayern Munich gives him more talent to work with than most of his previous employers, but Heynckes will no doubt be nervous about getting his first three points to break his own personal winless streak.
And in one of those ironic twists to which the gods of football seem to be addicted, Heyncke's first opponents with his new team are the squad with whom he himself is most closely associated -- Moenchengladbach.