With Silvio Berlusconi still at the helm, for the next four years the party worked tirelessly, mostly using the internet, to reflect the palpable change in mood among Italians - that they were fed up with the ruling class.
In February 2013, the party became the second biggest political force in Italy behind the centre-left Democratic Party (PD) after scooping 25 percent of the vote in the general election.
During the intervening years, most of that success was down to the protest nature of the group, with the burly Grillo – as much of a showman as Berlusconi - making a stand against everything from the euro and corruption to Italy's sclerotic political and economic system.
Beppe Grillo, leader of Italy's Five Star Movement. Photo: Filippo Monteforte/AFP
The party has since seized control of small cities, including Parma, Livorno and Ragusa, in Sicily, and on Sunday clinched two of its biggest prizes yet: the capital of Rome, and the former capital, Turin.
So how did the so-called ‘Grillini' get this far?
Possibly due to the party's leader taking a back seat. In January, the 67-year-old announced his return to the comedy circuit, not because he was distancing himself from the movement, he said, but simply “taking a step to the side”.
The move was preceded by a colourful few years, during which the party made headlines more for Grillo's tirades than for anything else.
Most of those, including telling a prostitute to ply her trade online because it's safer and making Nazi jibes at EU politicians, came in 2014 – the year he allied with Nigel Farage, the leader of Ukip, the British right-wing populist party.
Just a few weeks ago, Farage, who is campaigning for Britain to leave the EU ahead of a referendum on Thursday, told Corriere della Sera that the pair would “destroy the old EU” . “On June 19th, the Five Star Movement elects the mayor of the capital,” he said. “On June 23rd, Britain leaves the EU and changes Europe.”
Grillo also once said that he and Farage were “rebels with a cause”.
But 2014 was also the year Grillo, dubbed by the Italian media as ‘the clown', was advised by the party's co-founder and spin-doctor, the late Gianroberto Casaleggio, to tone down his aggression and “smile more”. The advice came during a post-mortem of the party's performance in the European Elections, which left it trailing behind the PD.
Grillo had kept a relatively low profile since then, with Luigi Di Maio, widely tipped to succeed him, working to transform the party, clean up its image and broaden its appeal. Grillo has also removed his name from the party's logo.
But he was back to his old tricks again in early May, sparking widespread condemnation after making a terrorist ‘joke' about London's new Muslim mayor, Sadiq Khan, during a show in Padua.
At the time, some commentators wondered if the gaffe risked damaging the party's chances in the impending mayoral elections. Not so.
So how come the turnaround?
Almost out of nowhere came Virginia Raggi, who was elected Rome's first-ever female mayor on Sunday.
An intellectual property lawyer and mother-of-one, Raggi has no experience of running anything.
But her pledge to crackdown on fare dodgers, improve public transport and clean-up the capital's streets struck a chord with the basic demands of an electorate that has long been weary of its political class.
With Rome's administration wracked by an ongoing trial over the infiltration of organized crime, and former mayor Ignazio Mario being ousted over an expenses scandal, Raggi also vowed to rid city hall of corruption.
Meanwhile in Turin, one of Italy's largest urban centres, the Five Star Movement's Chiara Appendino, 31, claimed just over 54 percent of the vote to oust the PD's long-serving Piero Fassino.
She became the city's third female mayor – after Maria Magnani Noya, elected in 1987, and Giovanna Cattaneo Incisa, who became mayor in 1992 but died within a year, aged 69. Noya died just a few days before, aged 80.
In their victory speeches, both Raggi and Appendino touched on their wins as being about “change” rather than “protest”.
"For the first time Rome has a female mayor in an age where equality of opportunity remains a mirage," Raggi said. "I will be a mayor for all Romans. I will restore legality and transparency to the city's institutions after 20 years of poor governance. With us a new era is opening."
Appendino, a multilingual businesswoman who helps run her family's laser equipment company, said: "We have made history. This was not a protest vote, it was about pride and change."
Has the party forged alliances with any others in order to win votes?
Since inception, one of the party's golden rules has been not to form any alliances with its opponents. Locally-elected representatives are also bound by a code of conduct that means they have to ask permission from the top for every important position.
So why else is the party so appealing right now?
That Italians MPs are among the highest paid in the world is well-known, and many voters have voiced their outrage by backing the Five Star Movement, whose representatives are forced to contribute part of their salaries towards reducing Italy's public debt and funding small businesses.
Raggi has vowed to tackle corruption in Rome. But are there any lurking threats to the party's image?
The party has been beating the drum about corruption since the beginning, but alas, its anti-graft banner has, in fact, been blackened by allegations it struck deals with local mobsters in Naples. Meanwhile, investigations have been launched into the Five Star's mayor of Parma for abuse of office, and his counterpart in the Tuscan city of Livorno is being probed for fraud.
Only time will tell if the Five Star Movement can truly break from Italian political tradition.