The move could affect the growth of legal downloading services, seen as vital to stifling the popularity of free file-swapping services such as Kazaa and Grokster.
E-Data has warned several European companies that it will not hesitate to launch further legal action if it finds they are infringing its "Freeny" patent.
The company owns the patent in 10 EU countries. It covers downloading and recording information, such as music, news articles or films, from a computer on to a tangible object, such as a tape, CD or sheet of paper.
Tibor Tallos, president of E-Data, said HMV and OD2 are in clear violation of the patent. "The website of HMV specifically permits the consumer to burn downloaded music onto a CD, or record it onto a portable playing device," he said. "We believe these activities are in clear violation of our patents. We intend to aggressively enforce our intellectual property to the full extent of the law."
HMV and OD2 said they were taking legal advice, but were not available to comment.