Exhibit 5.1

to Registration Statement

[Letterhead of Jones Walker LLP]

March 19, 2013

CenturyLink, Inc.

100 CenturyLink Drive

Monroe, Louisiana 71203

Re: Registration Statement on Form S-3

Ladies and Gentlemen:

We have acted as special counsel to CenturyLink, Inc., a Louisiana corporation (“CenturyLink”), in connection with the preparation of a registration statement on Form S-3 (the “Registration Statement”) filed with the Securities and Exchange Commission (the “Commission”) by CenturyLink. The Registration Statement relates to the registration of 900,000 shares of CenturyLink’s common stock, par value $1.00 per share the (“Common Stock”). 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 CenturyLink dated as of May 23, 2012; (ii) the amended and restated Bylaws of CenturyLink dated as of November 4, 2010; (iii) the resolutions adopted by the Board of Directors of CenturyLink on February 27, 2013 (the “Board Resolutions”); and (iv) such other records of CenturyLink, certificates of CenturyLink’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 CenturyLink and documents furnished to us by CenturyLink without independent verification of their accuracy. We have also assumed the genuineness of all signatures, the authenticity of all documents submitted to us as originals, the conformity to original documents of all documents submitted to us as certified or photostatic copies and the authenticity of the originals of such documents.

Based upon the foregoing and subject to the following qualifications and comments, we are of the opinion that:

CenturyLink, Inc.

March 19, 2013

Page 2

1. CenturyLink is a corporation duly organized, validly existing and in good standing under the laws of the State of Louisiana and has all requisite corporate power to issue the Common Stock; and

2. Upon issuance in the manner described in the Registration Statement, the Common Stock will be legally issued, fully paid and non-assessable.

The opinions rendered herein are specifically limited to currently applicable laws of the State of Louisiana as they relate to the opinions expressed herein. We express no opinion as to the application of the securities or blue sky laws of the various states to the sale of any shares of Common Stock.

This letter is limited to the specific issues addressed herein, and no opinion may be inferred or implied beyond that expressly stated herein. This letter speaks only as of the date hereof. We assume no obligation to revise or supplement this letter should the presently applicable laws be changed by legislative action, judicial decision or otherwise.

We consent to the filing of this letter as an exhibit to the Registration Statement and to the reference to us in the prospectus under the caption “Legal Matters.” In giving this consent, we do not admit that we are within the category of persons whose consent is required under Section 7 of the Act or the general rules and regulations of the Commission.

Very truly yours,

/s/ Jones Walker LLP

Jones Walker LLP