Security firm Trend Micro said that the ads appeared as Flash media-format files on the sites.
Users clicking on the ads were redirected to malicious sites which then attempted to install a rogue anti-spyware application.
A spokesperson for Rhapsody owner RealNetworks said that it had first received reports of the ads on 20 January.
The company conducted its own investigation and the malicious files had been removed by 24 January.
The malicious Expedia ads, which advertised a music download service, were
disclosed on 28 January by Australian spyware researcher Sandi Hardmeir, who notified the company immediately.
An Expedia spokesperson said that the ads have been removed, and that the company is investigating how long they were online.
Ad firm DoubleClick fell victim to a similar attack late last year which resulted in malicious ads appearing on official sites belonging to Major League Baseball, National Hockey League and The Economist.
"This provides yet another method for cyber-criminals to effectively spread malicious code and earn illicit profits at the same time," wrote Trend Micro researcher Bernadette Irinco on a
company blog.
"There is no doubt that cyber-criminals will continue with their 'malvertising' campaigns, targeting more and more popular sites to 'advertise' their malware."
Ad networks have long been locked in a struggle with the purveyors of malicious software.
Malware dealers often use bait-and-switch tactics, presenting the network with a legitimate ad which is later replaced with a malicious file.