Security researchers at Lookout found 32 apps on Google Play that were infected by malware called BadNews.
The malware sends messages to premium rate text numbers. It is designed to lay dormant for weeks after being downloaded to avoid detection.
Premium rate malware is prolific in Eastern Europe and Russia.
Experts have warned that despite stronger regulation and monitoring, Western European and North American based criminals could still attempt to replicate the malware.
The malware specifically targeted Android owners in Russia, Ukraine, Belarus and a number of other Eastern European customers.
Lookout said it was difficult to estimate how many handsets could have been infected before Google finally removed the apps. It estimates between two and nine million infected apps may have been downloaded.
Amongst the apps BadNews was found in were recipe generators, wallpaper apps, games, and porn apps.
All of the infected apps were released by four separate accounts. They have since been suspended.
According to Lookout, the infected apps tricked users into installing what was described as an update for either Skype or popular Russian social network Vkontakte. It then started stealing credit by sending texts to premium rate numbers.
The firm also said it was concerned that many of the developers had included the code in their apps willingly. Lookout said many had been convinced BadNews was little more than a advert network.
It urged developers to be more careful about the third party code they use in their apps.
In the past, major security companies – including Russian firm Kaspersky – have criticised Google for putting its users at unnecessary risk.