Exhibit 5.1

[LETTERHEAD OF WILLIAM L. HORTON, JR.]

July 9, 2015

Re: Verizon Communications Inc. Registration Statement

on Form S-4 under the Securities Act of 1933

Ladies and Gentlemen:

Reference is made to the Registration Statement on Form S-4 (the “Registration Statement”) which Verizon Communications Inc., a Delaware corporation (the “Company”), is filing with the Securities and Exchange Commission under the Securities Act of 1933, as amended (the “Securities Act”), pertaining to the offer by the Company to exchange (i) up to $2,868,704,0000 aggregate principal amount of its outstanding 4.272% notes due 2036 for a like principal amount of its 4.272% notes due 2036 that have been registered under the Securities Act (the “Exchange Notes due 2036”), (ii) up to $5,000,000,000 aggregate principal amount of its outstanding 4.522% notes due 2048 for a like principal amount of its 4.522% notes due 2048 that have been registered under the Securities Act (the “Exchange Notes due 2048”) and (iii) up to $5,499,999,000 aggregate principal amount of its outstanding 4.672% notes due 2055 for a like principal amount of its 4.672% notes due 2055 that have been registered under the Securities Act (the “Exchange Notes due 2055,” and together with the Exchange Notes due 2036 and the Exchange Notes due 2048, the “Exchange Notes”), each as described in the Registration Statement and the accompanying Prospectus.

I, or attorneys under my direction, have reviewed the Registration Statement, the Company’s Restated Certificate of Incorporation and Bylaws, resolutions adopted by the Board of Directors of the Company, and such other documents and records as I have deemed appropriate for the purpose of giving this opinion.

Based upon the foregoing, I am of the opinion that:

1. The Company is a corporation duly incorporated, validly existing and in good standing under the laws of the State of Delaware.

2. The Exchange Notes, upon the issuance and sale thereof in the manner contemplated in the Registration Statement and the indenture referenced in the Prospectus, will be legally issued and will be binding obligations of the Company, except to the extent that enforcement may be limited by bankruptcy, insolvency, reorganization, moratorium, fraudulent conveyance or transfer, or similar laws of general applicability affecting the enforceability of creditor’s rights.

I express no opinion as to matters governed by any laws other than the laws of the State of New York, the Federal laws of the United States of America and the corporate laws of the State of Delaware.

I hereby consent to the filing of this opinion with the Securities and Exchange Commission in connection with the Registration Statement and to being named under the heading “Legal Matters” in the Prospectus forming part of the Registration Statement.

Very truly yours,

/s/ William L. Horton Jr.