The most downloaded iPhone app in the US, according to research by comScore, is Facebook. In the UK, tellingly, it's iPint from Carling, but in Europe it's Shazam.

The music discovery service that identifies a piece of recorded music via a mobile's mic reached a total of 50million users across all platforms in October 2009 (15million on the iPhone). The goal is to double this figure by the end of 2010.

Even the fact that five months ago the London-based startup introduced a paid-for version of its iPhone app – Shazam Encore – and limited the free version to five tags per month for new users doesn't seem to have stood in its way.

"The reason we introduced Encore," explains CEO Andrew Fisher, "is because we had a lot of user feedback saying that people felt Shazam was worth paying for. We also wanted to converge with other platforms because, outside of the iPhone, we do charge.

"The hardest part was educating people that we'd changed our business model. We didn't remove the experience for existing users: people could continue to use Shazam on an unlimited basis. Encore is really for new users that then came into the service from November onwards."

Encore, which is available for a one-off payment of £2.99, comes with a new design, unlimited tagging, faster performance and a range of extra features such as music search and geolocation ticketing. When you tag a song, Shazam now determines where you are and tells you if that artist is playing concerts in your area (or in a radius of 25 miles) and gives you the chance to buy tickets directly through the app. There's also music recommendations.

"A lot of people think of us just as a music recognition service, but actually our strategy is to help people discover a song they like, be able to buy the song and share that experience via Twitter and Facebook.

"We've seen very high usage of the recommendations engine, and we do collaborative filtering, so if you and I both tagged the same track, there's a correlation between all the other songs we've identified. We present the strongest correlation, which means that the recommendations tend to be very accurate around a particular genre of music."

However, Fisher insists Shazam isn't trying to compete with Pandora or Last.fm. In fact, it's just announced Encore's integration with both services. "People can take advantage of their Pandora and Last.fm accounts to use Shazam to discover music. If they want to create a radio station or listen to the music via a stream, they can go directly from the tag results page to their Last.fm or Pandora account. It's complementary.

"There's no company that completes the whole music experience. We want to create a very seamless experience for the consumer, so Shazam becomes the entry point."

No phoney

Although Shazam as a company has been around for 10 years (it started as a text service), the turning point came with the release of the first iPhone app in 2008. Around the same time Shazam became profitable, and the user base started growing exponentially.

"It's true we had tremendous support from Apple, particularly in North America," Fisher says. "We're growing with the iPhone and 15million people on the iPhone is a reasonable proportion, but there are 4.5billion mobile phones in the world today, as opposed to 1.7billion PCs. Our success milestone is to get to 100million people that have used Shazam, but that's still only two per cent of the market.

"There really hasn't been a company that's just focused on the mobile and built its audience around that. That's our goal and we don't expect to be alone. We expect four or five companies to have very large audiences with more than 300million users in the next five years.

"Most companies are focused on the iPhone, Android, RIM and other platforms but we're committed to supporting mid-or low-end handsets in regions such as Latin America, Africa, the Middle East and certain parts of Asia-Pacific as well, because unless you support those devices you're not going to build a company that has 250million users. Our strategy is to be ubiquitous and in order to achieve that goal, we need to build for those other handsets."

Every day Shazam identifies two million songs, and every week 750,000 new users are discovering the service. Eight per cent of people who tag a track go on to purchase it on affiliate stores. That's around 160,000 tracks daily. It has turned Shazam into iTunes' biggest reseller on mobile. So what actually happens when you hold your phone in the air?