The deal marks the second time in less than three months that Netflix Inc. has anted up for a more direct connection to a major Internet service, even though CEO Reed Hastings objects to having to pay for better access.
Netflix negotiated a similar arrangement with Comcast Corp. in February.
The financial details of Netflix's partnerships with Comcast and Verizon Communications Inc. haven't been disclosed.
Netflix is reducing its reliance on third-party vendors to deliver video to Internet service providers because the streaming speeds of its movies and TV shows have been slowing in recent months.
The company hopes the Verizon deal "will improve performance for our joint customers over the coming months," Netflix spokesman Joris Evers said Tuesday. Verizon issued a similar statement.
Netflix has nearly 36 million U.S. subscribers to its Internet video service, which charges $8 per month in the U.S. About 9 million customers pay Verizon for high-speed online access in their homes and businesses.
With its Comcast partnership in place, Netflix says the quality of its video on that network has improved dramatically. In March, Netflix's video streamed at an average of 2.5 megabits per second, a 66 percent increase from January. The higher speeds translate into a richer and steadier picture.
Netflix's video streamed at an average of 1.91 megabits per second on Verizon's Internet service in March.
Although Hastings has publicly complained about having to pay Internet service providers for more direct connections, it's not clear the deals will cost Netflix more money. That's because Netflix already had been paying content-delivery fees to third-party vendors such as Cogent Communications Group Inc.
In a blog post last week, Comcast asserted that its deal will enable Netflix to reduce its expenses.
Netflix didn't directly address that claim in its own blog post deriding Comcast last week. Instead, Netflix accused Comcast of "double dipping" by charging to deliver content that many of its subscribers want to watch. Netflix has become so popular that it generates nearly one-third of the evening traffic on the Internet in the U.S., according to the research firm Sandvine.
The Netflix traffic is straining some networks and raising tensions with Internet service providers who argue they shouldn't have to shoulder all the financial burdens for handling all the extra traffic.
Even though Netflix is now working with Comcast, their relationship remains antagonistic. In the most visible sign of discord, Netflix is opposing Comcast's proposed $45 billion acquisition of rival Time Warner Cable Inc. because it believes the combination will give Comcast too much control over the prices that both consumers and websites pay for Internet access.
Netflix Inc., which is based in Los Gatos, Calif., plans to raise its prices by $1 or $2 for new customers only within the next two months.