QuickLinks -- Click here to rapidly navigate through this document

Exhibit 5.1

March 25, 2005

(212) 351-4000 C 93166-00083

(212) 351-4035

Qwest Corporation
1801 California Street
Denver, Colorado 80202

Re:

Qwest Corporation
Registration Statement on Form S-4

Ladies and Gentlemen:

        We have acted as counsel for Qwest Corporation, a Colorado corporation (the "Company"), in connection with the Company's offer (the "Exchange Offer") to issue and exchange up to $825,000,000 aggregate principal amount of its 7.875% Notes due 2011 (the "Exchange Notes"), which are to be registered under the Securities Act of 1933, as amended (the "Act"), for a like principal amount of its outstanding 7.875% Notes due 2011 (the "Outstanding Notes"). The Outstanding Notes were, and the Exchange Notes will be, issued under the Indenture dated as of October 15, 1999 (the "Base Indenture"), between the Company and J.P. Morgan Trust Company, National Association (as successor in interest to Bank One Trust Company, N.A.), as trustee, as supplemented by a first supplemental indenture dated as of August 19, 2004 (the "First Supplemental Indenture"), between the Company and U.S. Bank National Association, as trustee (the "Trustee"), and a second supplemental indenture dated as of November 23, 2004, between the Company and the Trustee (the "Second Supplemental Indenture," and together with the Base Indenture and the First Supplemental Indenture, the "Indenture"). Capitalized terms not otherwise defined herein shall have the meanings set forth in the Indenture.

        We have examined, among other things, the Indenture and the form of the Exchange Notes. In addition, we are familiar with the Company's above referenced Registration Statement on Form S-4 (the "Registration Statement") filed by the Company with the Securities and Exchange Commission to register under the Act the issuance of the Exchange Notes in the Exchange Offer. The Indenture and the Exchange Notes are sometimes referred to herein collectively as the "Documents." We have also made such other inquiries and examined, among other things, originals or copies, certified or otherwise identified to our satisfaction, of such records, agreements, certificates, instruments and other documents as we have considered necessary or appropriate for the purposes of this opinion.

        In rendering this opinion, we have assumed without independent verification:

        (a)   the signatures on all documents examined by us are genuine, all individuals executing such documents had all requisite legal capacity and competency, the documents submitted to us as originals are authentic, the documents submitted to us as certified or reproduction copies conform to the originals, and all such documents are binding on all persons (other than the Company) signing such documents; and

        (b)   the issuance and delivery of the Exchange Notes will not, at any time, violate any applicable law or result in a violation of any provision or any instrument or agreement then binding on the Company or any restriction imposed by any court or governmental body having jurisdiction over the Company.

        Based upon the foregoing and in reliance thereon, and subject to the assumptions, exceptions, qualifications and limitations contained herein, we are of the opinion that the Exchange Notes, when executed and authenticated in accordance with the provisions of the Indenture and issued and delivered in exchange for the Outstanding Notes in the manner described in the Registration Statement, will be legally issued and binding obligations of the Company.

        The foregoing opinion is subject to the following exceptions, qualifications and limitations:

        A.    We are admitted to practice in the States of New York and Colorado and express no opinion as to matters governed by any laws other than the laws of the State of New York, the State of Colorado and the federal laws of the United States of America. This opinion is limited to the effect of the present state of the laws of the State of New York, the State of Colorado and of the United States of America and the facts as they presently exist.

        B.    Our opinion is subject to (i) the effect of any bankruptcy, insolvency, reorganization, moratorium, arrangement or similar laws affecting any rights and remedies of creditors generally (including, without limitation, the effect of statutory or other laws regarding fraudulent transfers or preferential transfers) and (ii) general principles of equity, including without limitation 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.

        C.    We express no opinion regarding (i) the effectiveness of any waiver (whether or not stated as such) under the Documents of, or any consent thereunder relating to, any stay, extension or usury laws or any unknown future rights or the rights of any party thereto existing, or duties owing to it, as a matter of law; (ii) the effectiveness of any waiver (whether or not stated as such) contained in the Documents of rights of any party, or duties owing to it, that is broadly or vaguely stated or does not describe the right or duty purportedly waived with reasonable specificity; (iii) provisions relating to indemnification, exculpation or contribution, to the extent such provisions may be held unenforceable as contrary to public policy or federal or state securities laws or due to the negligence or willful misconduct of the indemnified party; (iv) any provisions of the Documents that may be construed as penalties or forfeitures; or (v) the effectiveness of any covenants (other than covenants relating to the payment of principal, interest, indemnities and expenses) to the extent they are construed to be independent requirements as distinguished from conditions to the declaration or occurrence of a default or any event of default.

        D.    We have assumed that there are no agreements or understandings between or among the parties to the Documents or third parties that would expand, modify or otherwise affect the terms of the Documents or the respective rights or obligations of the parties thereunder.

        E.    We express no opinion concerning the Modification of Final Judgment entered August 24, 1982 in United States v. Western Electric et al., Case No. 82-0192, United District Court, District of Columbia, as amended, modified, supplemented or interpreted by a court of competent jurisdiction from time to time.

        We hereby consent to the filing of this opinion as an exhibit to the Registration Statement, and we further consent to the use of our name under the caption "Legal Matters" in the prospectus forming a part of said Registration Statement. In giving these consents, we do not thereby admit that we are within the category of persons whose consent is required under Section 7 of the Act, or the rules and regulations promulgated thereunder.

Very truly yours,

/s/ Gibson, Dunn & Crutcher LLP

2

QuickLinks

Exhibit 5.1