Analysts said this new departure might even see Faymann's Social Democrats (SPÖ) taking the radical and dangerous gamble of dropping its historic opposition to a tie-up with the far-right.
The SPÖ and their centre-right "grand coalition" partners the People's Party (ÖVP) have dominated Austrian politics since World War II but their support has been sliding for years.
During the last general election in 2013, they only just scratched together a majority, and polls suggest they will fail to do so again at the next ballot in 2018. In the recent presidential election, the two ruling parties' candidates were knocked out the first round with just 11 percent of the vote.
Deputy Chancellor Reinhold Mitterlehner, head of the ÖVP, will replace Faymann on an interim basis but it was unclear who would be his permanent successor as chancellor and SPÖ boss.
Two possible candidates are Christian Kern, 50, head of the national railways company, and Gerhard Zeiler, 60, former chief of national broadcaster ORF. A decision may be taken at a party meeting on May 17.
"It would be good to have a new face, someone from outside the party," Karin Cvrtila from the OGM polling institute told AFP.
But, Cvrtila said, they will have a momentous decision to take: whether to stick with the SPÖ's traditional opposition to the FPÖ, or to team up with it, as the party has done in the eastern state of Burgenland.
Such a move has been backed by party grandee and former chancellor Franz Vranitzky, among many others. Cvrtila said it would be "smart" not to rule out some sort of cooperation.
But such a move could also tear the SPÖ apart. Political analyst Anton Pelinka from Innsbruck University called it "very dangerous", saying it could potentially drive voters towards the Greens.
"The SPOe is completely stumped and confused," he said.
History also serves as a warning. When in 2000, the ÖVP formed a government with the far-right Freedom Party (FPÖ) under the late Joerg Haider, the result was massive demonstrations and Austria being ostracised in Europe.
SPÖ bleeding support
Mirroring similar trends across Europe, the centre-left SPÖ has been bleeding support to fringe groups, which in Austria's case means the anti-immigration FPÖ, now headed up by Heinz-Christian Strache.
On April 24, the FPÖ candidate won the first round of elections for the largely-ceremonial post of president and will face the Green-backed independent candidate Alexander van der Bellen in the run-off on May 22nd.
The dismal performance of the two ruling parties, due also to a worsening economic situation and the coalition's inability to agree reforms, means that for the first time since 1945, the president will not be from one of the two centrist parties.
This could result in a situation in which the new president makes use of some of the head of state's considerable but hitherto unused powers, such as firing the government or dissolving parliament.