"I think that Elop will have to go but I also think that the board also needs to be renewed with people who have an understanding and working knowledge of the mobile industry," Gassée told Computing.co.uk.
"The board of Nokia were already thinking that Kallasvuo should go. They made no bones about their dissatisfaction with the top management," Gassée said.
"I told them to drop everything and go Android. Do it in secret and let the rumours fly. I would have used Nokia's design flare to make very nice phones. I would integrate Ovi [Nokia's app store] into Android and people would say that Nokia sided with the winner."
Some in the industry feel Nokia could still switch to Android, with Chairman of Nokia's board of directors Risto Siilasmaa admitting the company has a backup plan. However, Gassée said the biggest thing standing in the way of Nokia's success with Android is Korean manufacturer Samsung, which makes the popular Galaxy S3 and Note handsets.
"It would have been tough fighting Samsung though, because Samsung takes no prisoners. They don't brush their teeth in the morning, they file them," said Gassée.
Nokia heeded his advice and fired Kallasvuo but did not adopt Android because the company would "lose control of their destiny", Gassée says Nokia told him.
Gassée criticised current Nokia CEO Elop for two major errors: his "burning platform" memo in February 2011 and Microsoft's recent announcement on Windows Phone 8.
In February 2011 Elop described Symbian as being like the platform of a burning oil rig in the North Sea which Nokia had to escape from. The comments in a memo on an internal blog were leaked to the media.
In April 2012, Microsoft revealed that there will be no way for smartphones running Windows Phone 7 to upgrade to Windows Phone 8 when the OS is released later this year. That includes the Nokia Lumia range and could impact the sale of phones designed to kick start Nokia's comeback.
"Microsoft can do that with new versions of Windows, IBM used to do that in the olden days. But I'm shocked that the board of Nokia allowed Elop to do that," Gassée said.
While acknowledging that Elop inherited a company facing a lot of challenges, Gassée questioned whether he was the right man for the job. "He [Elop] has zero experience in terms of what makes a smartphone maker tick. And what is his experience in supply chain management? Zero," said Gassée.
Nokia's Elop was not named in Forbes' list of the five current CEOs it believes should already have been fired. Microsoft's Steve Ballmer was singled out as the worst by Forbes, while the list also contained Cisco Systems' John Chambers, Mike Duke at WalMart, Edward Lampert of Sears Holdings and Jeffrey Immelt at GE.