Exhibit 5.1

September 2, 2015

CenturyLink, Inc.

100 CenturyLink Drive

Monroe, Louisiana 71203

Re: CenturyLink, Inc.

5.625% Senior Notes, Series X, due 2025

Ladies and Gentlemen:

We have acted as special counsel to CenturyLink, Inc., a Louisiana corporation (the “Company”), in connection with the preparation of the registration statement on Form S-4 (as amended, the “Registration Statement”) filed by the Company with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Securities Act”), on or about the date hereof with respect to the Company’s offer to exchange (the “Exchange Offer”) up to $500 million aggregate principal amount of the Company’s unregistered 5.625% Senior Notes, Series X, due 2025 (the “Unregistered Notes”) for a like principal amount of the Company’s registered 5.625% Senior Notes, Series X, due 2025 (the “Registered Notes” and together with the Unregistered Notes, the “Notes”). The Unregistered Notes have been, and the Registered Notes will be, issued pursuant to an indenture dated as of March 31, 1994, between the Company and Regions Bank (the “Trustee”) (successor-in-interest to First American Bank and Trust of Louisiana and Regions Bank of Louisiana) (the “Base Indenture”), as amended and supplemented from time to time, including the tenth supplemental indenture thereto establishing the terms of the Notes (the “Supplemental Indenture”, and together with the Base Indenture, the “Indenture”).

In connection with rendering the opinions expressed below, we have examined originals, or copies certified or otherwise identified to our satisfaction, of such corporate records, certificates of corporate officers and government officials and such other documents as we have deemed necessary or appropriate for the purposes of this opinion, including: (i) the amended and restated Articles of Incorporation of the Company dated as of May 23, 2012; (ii) the amended and restated Bylaws of the Company as amended through May 23, 2014; (iii) the resolutions adopted by the Board of Directors of the Company on February 23, 2015; (iv) the resolutions adopted by the Special Pricing Committee of the Board of Directors of the Company on March 12, 2015; (v) the Indenture; and (vi) such other records of the Company, certificates of the

Company’s officers and public officials, and such other documents as we have deemed relevant. As to various questions of fact material to this opinion, we have relied upon representations of officers or directors of the Company and documents furnished to us by the Company without independent verification of their accuracy and upon such other documents, records, certificates and other instruments, including certificates or other written or oral advice of public officials and officers of the Company, as we considered necessary or appropriate in connection with rendering the opinions expressed below.

In our examination of such documents, we have assumed without independent verification (i) that each of the documents and instruments reviewed by us has been duly authorized, executed and delivered by each of the parties thereto other than the Company and is enforceable against such parties in accordance with the terms thereof, (ii) the authenticity of all documents and instruments submitted to us as originals, (iii) the conformity to the originals of all documents and instruments submitted to us as conformed, certified or photostatic copies, (iv) the accuracy and completeness of all corporate records made available to us by the Company and its subsidiaries, (v) the absence of any other documents, instruments, records, agreements or understandings that alter, modify or change the validity or accuracy of the representations made to us orally or as set forth in any documents, instruments, records or agreements provided to or reviewed by us, (vi) the genuineness of all signatures on all documents and instruments examined by us, and (vii) the power and legal capacity of all persons (other than the Company and its subsidiaries) who have executed documents reviewed by us hereunder.

Based upon the foregoing and subject to the assumptions, exceptions, qualifications and limitations set forth hereinafter, we are of the opinion that when (a) the Registration Statement has become effective under the Securities Act, (b) the Unregistered Notes have been exchanged in the manner described in the prospectus forming a part of the Registration Statement, (c) the Registered Notes have been duly executed, authenticated, issued and delivered by the Company in accordance with the terms of the Indenture, against receipt of the Unregistered Notes surrendered in exchange therefor, and (d) the Indenture has been duly qualified under the Trust Indenture Act of 1939, as amended, the Registered Notes proposed to be issued pursuant to the Exchange Offer will be valid and binding obligations of the Company.

The opinions and other matters in this letter are qualified in their entirety and subject to the following:

A. We express no opinion other than as to the laws of the State of Louisiana (the “Laws”). We assume no obligation to revise or supplement this opinion to reflect any facts or circumstances that may hereafter come to our attention or to reflect any subsequent changes in applicable Laws by legislative action, judicial decision or otherwise.

B. Our opinion expressed above is subject to the qualification that enforceability may be limited by (i) applicable bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium or similar laws of general applicability relating to or affecting the enforcement of creditors’ rights, (ii) general principles of equity (regardless of whether enforceability is considered in a proceeding in equity or at law) including without limitation concepts of materiality, reasonableness, good faith and fair dealing, (iii) public policy considerations that may limit the rights of parties to obtain certain remedies, (iv) laws or public policy

2

considerations that may limit the enforceability of provisions relating to indemnification, exculpation or contribution, (v) the effects of applicable laws requiring the mitigation of damages and (vi) limitations on the waiver of rights under any stay, extension or usury law or other law, whether now or hereafter in force, which would prohibit or forgive the Company from paying all or any portion of the Unregistered Notes or the Registered Notes as contemplated in the Indenture.

We hereby consent to the filing of this opinion with the Commission as Exhibit 5.1 to the Registration Statement. We also consent to the reference to our firm under the caption “Legal Matters” in the Registration Statement. In giving this consent, we do not thereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission promulgated thereunder.

Very truly yours,

/s/ Jones Walker L.L.P.

Jones Walker L.L.P.

3