When it comes to digital music, you have to be a hard-ass at the negotiating table, Spotify founder Daniel Ek told Sarah Lacy at PandoMonthly tonight.

Music labels are notoriously difficult to deal with and have endured a lot of criticism in recent years for being slow to adapt to the digital age. So being smart in dealing with those companies was crucial to protecting Spotify’s integrity and ensuring its long-term success. “You have to lead with your conviction in the product,” Ek said.

It paid off. Spotify now has one of the most comprehensive music libraries in the world, with tens of millions of songs and agreements with all the major labels. Since launching just over a year ago, it has acquired more than 3 million users, 20 percent of whom are paying customers. Some of its US competitors haven’t been so successful, Ek said.

“I think what happened with a lot of these Valley companies was that they ultimately compromised on economic concerns, and then eventually had to compromise the product, or they just immediately compromised the product,” he said.

Lacy also asked Ek why it took so long for Spotify to launch in the US. That came down to making sure the company had the right deals in place, Ek said. “It wouldn’t have been that hard to launch in the US, if all we wanted to do was a subscription service, or if all we wanted to do was another download service. But we wanted to launch a product that a user thought was free, that meant that they could share tracks with their friends, that meant that they could try out the whole experience before they later decided if they wanted to convert.”

That unwillingness to compromise is key to building a great company, Ek believes. The company started negotiations to launch in the US just two months after it launched in Europe in 2008. It didn’t arrive in the US until July 2011. It came close numerous times in the interim, but sometimes deals would fall through at the last signature. Spotify didn’t want to enter the market without getting its way.

“There are other companies that act that way too,” Ek said. “Apple is one of them, and many, many times throughout the years, [they] stopped at the last minute, even though they built the product, because they couldn’t get the deal that they wanted in order to preserve the user experience.”

He added: “It’s super important to never compromise on what you think is a great user experience, because it will deteriorate.”

Throughout the process, Spotify’s investors kept their distance while offering their full support. “We knew that this was going to be our mission,” said Ek, “and while we were open to feedback, it’s not like we were going to say, ‘Alright, we’re going to turn around and pivot.’”

“We said to everyone that this is a company that’s either going to fly, or it’s going to crash and burn. It’s not going to just be an okay one.”