Exhibit 5.1

Arthur Saltarelli

Associate General Counsel

CenturyLink

1801 California Street, 10^th Floor

Denver, CO 80202

June 25, 2012

Qwest Corporation

100 CenturyLink Drive

Monroe, Louisiana 71203

Re: Qwest Corporation 7.00% Notes due 2052

Ladies and Gentlemen:

I am Associate General Counsel of CenturyLink, Inc., a Louisiana corporation (“CenturyLink”), and am providing this letter as counsel to Qwest Corporation, a Colorado corporation and wholly owned subsidiary of CenturyLink (the “Company”). I have examined the Registration Statement on Form S-3, File No. 333-179888-01 (the “Registration Statement”) of CenturyLink and the Company filed with the Securities and Exchange Commission (the “Commission”) pursuant to the Securities Act of 1933, as amended (the “Securities Act”), the prospectus included therein, and the prospectus supplement, dated June 14, 2012, filed in definitive form by the Company with the Commission on June 18, 2012, pursuant to Rule 424(b) of the Securities Act (the “Prospectus Supplement”) in connection with the offering and sale by the Company of $400,000,000 aggregate principal amount of the Company’s 7.00% Notes due 2052 (the “Securities”).

The Securities will be issued pursuant to an Indenture, dated as of October 15, 1999, between the Company (formerly named US WEST Communications, Inc.) and Bank of New York Trust Company, National Association (as successor in interest to Bank One Trust Company, N.A. and J.P. Morgan Trust Company, National Association), as amended and supplemented to the date hereof, and as will be further supplemented by the Eleventh Supplemental Indenture between the Company and U.S. Bank National Association, as trustee, dated as of June 25, 2012 (as amended and supplemented, the “Indenture”).

In rendering the opinions expressed below, I have examined the originals, or copies identified to my satisfaction as being true and complete copies of the originals, of such records of the Company and certificates of individuals and such other documents as I have deemed relevant and necessary as the basis for these opinions. In my examination, I have assumed the genuineness of all signatures, the legal capacity and competency of all natural persons executing agreements, instruments or documents, the completeness and authenticity of all documents submitted to me as originals and the conformity with originals of all documents submitted to me as copies.

Based upon the foregoing and in reliance thereon, and subject to the assumptions, exceptions, qualifications and limitations set forth herein, I am of the opinion that the Securities have been duly authorized on behalf of the Company and that, assuming the Securities are duly executed, authenticated, issued and delivered as provided in the Indenture and issued and delivered to the Underwriters (as defined below) against payment therefor in accordance with the terms of the Underwriting Agreement, dated June 14, 2012, between the Company and the several underwriters named in Schedule I thereto (the “Underwriters”), the Securities will constitute legal, valid and binding obligations of the Company.

June 25, 2012

Page 2

The opinions expressed above are subject to (i) the effect of any bankruptcy, insolvency, reorganization, moratorium, arrangement or similar laws affecting the rights and remedies of creditors’ generally, including the effect of statutory or other laws regarding fraudulent transfers or preferential transfers, and (ii) general principles of equity, including concepts of materiality, reasonableness, good faith and fair dealing and the possible unavailability of specific performance, injunctive relief or other equitable remedies regardless of whether enforceability is considered in a proceeding in equity or at law.

I consent to (i) the filing of this opinion with the Commission as an exhibit to the Company’s Current Report on Form 8-K, dated June 25, 2012, (ii) the incorporation by reference of this opinion into the Registration Statement, and (iii) the use of my name under the caption “Legal Matters” in the Registration Statement and the Prospectus Supplement. In giving these consents, I do not thereby admit that I am within the category of persons whose consent is required under Section 7 of the Securities Act.