Under the agreement, Spiralfrog will offer Universal's songs online in the US and Canada.
New York-based Spiralfrog will launch its service in December and make its money by carrying adverts on the site.
Spiralfrog aims to take on market leader Apple's iTunes service, which charges 99 cents per song in the US.
"Offering young consumers an easy-to-use alternative to pirated music sites will be compelling," Spiralfrog Chief Executive Robin Kent said.
Mr Kent, the former head of the Universal McCann advertising agency, added that his research suggested that in return for free music, young people would be willing to endure adverts - as long as the brands and products were relevant to them.
US-based music industry legal specialist Josh Lawler said news of the new service was "inevitable".
| || Spiralfrog will have to find a way to pay artists from the advertising dollars they are generating |
Josh Lawler, music industry specialist
"It's a very shrewd move by Universal," he told BBC News.
"The music industry is going to a point where all delivery will probably be some form of downloading or streaming."
Figures from the International Federation of Phonographic Industries (IFPI) estimate that for each legal download, 40 are done illegally.
Mr Lawler added that the success of Myspace had underlined the power of the internet to make or break artists - as well as proving that advertising-based formats can work.
But while Spiralfrog is discussing possible deals with other big record firms, questions still remain over how the artists featured on Spiralfrog will be paid.
"The internet is very much a viable media, but the trick is going to be getting it off the ground in the first place," Mr Lawler added.
"Spiralfrog will have to find a way to pay artists from the advertising dollars they are generating.
"But they're not necessarily going to know how many advertising dollars there are and so some artists are going to be hesitant about it," he said.
The music downloads industry is a burgeoning market. According to the IFPI, 60 million MP3 players were sold in 2005, while 420 million single tracks were downloaded during the year - up 20 times on two years earlier.
| || |
60m MP3 players sold worldwide
420m single tracks downloaded
Revenues from music downloads for MP3s and mobile phones totalled $1.1bn
350 legitimate download sites in 2005, up from 50 in 2003*Source: IFPI Digital music report 2006
Many of the models sold are also expected to be incompatible with Apple's online record store - such as Sony's Walkman.
At the same time, numerous companies are jumping on the downloads bandwagon.
Entertainment retailers HMV and Virgin already offer music downloads, while music television channel MTV has opened its own online shop, Urge.
Microsoft is preparing to launch a music store to go with its Zune player, made by Toshiba, which is popularly viewed in the industry as an "iPod killer".