Exhibit 5.1

November 26, 2012

Telephone and Data Systems, Inc.

30 North LaSalle Street

Suite 4000

Chicago, Illinois 60602

Re:                             Telephone and Data Systems, Inc.

$175,000,000 of 5.875% Senior Notes due 2061

Ladies and Gentlemen:

We are counsel to Telephone and Data Systems, Inc., a Delaware corporation (the “Company”), and have represented the Company with respect to the Registration Statement on Form S-3 (Registration No. 333-176835) (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”), which Registration Statement became effective upon filing pursuant to Rule 462(e) under the Securities Act.  Pursuant to the Registration Statement, the Company is issuing $175,000,000 aggregate principal amount of the Company’s 5.875% Senior Notes due 2061 (the “Securities”). The Securities are being issued under an Indenture dated November 1, 2001 between the Company and The Bank of New York Mellon Trust Company, N.A. (formerly known as The Bank of New York Trust Company, N.A., as successor to BNY Midwest Trust Company), as trustee (the “Trustee”), as supplemented by the First Supplemental Indenture dated November 28, 2001, the Second Supplemental Indenture dated May 31, 2002, the Third Supplemental Indenture dated March 23, 2005, the Fourth Supplemental Indenture dated November 16, 2010, the Fifth Supplemental Indenture dated March 21, 2011 and the Sixth Supplemental Indenture dated November 26, 2012 (as so supplemented, the “Indenture”).

This opinion letter is being delivered in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act.

In rendering this opinion letter, we have examined and relied upon a copy of (i) the Registration Statement, (ii) the Company’s prospectus dated November 26, 2012 included in the Registration Statement (the “Base Prospectus”), (iii) the Company’s prospectus supplement dated November 26, 2012 supplementing the Base Prospectus and relating to the Securities, (iv) the Indenture, (v) the Securities in global form, (vi) the executed Underwriting Agreement dated

Sidley Austin LLP is a limited liability partnership practicing in affiliation with other Sidley Austin partnerships

November 26, 2012 (the “Underwriting Agreement”) among the Company and Citigroup Global Markets Inc., Merrill Lynch, Pierce, Fenner & Smith Incorporated, UBS Securities LLC and Wells Fargo Securities, LLC as representatives of the several underwriters named in the related Terms Agreement dated November 26, 2012, relating to the issuance and sale of the Securities, (vii) certain resolutions of the Board of Directors of the Company adopted on October 12, 2001, August 27, 2008, November 3, 2010 and November 16, 2012 and of the Pricing Committee of the Board of Directors of the Company duly adopted on November 26, 2012, as certified by the Secretary of the Company on November 26, 2012 as being true, complete and correct and in full force and effect, relating to, among other things, the authorization of the Registration Statement and the issuance and sale of the Securities and (viii) the Restated Certificate of Incorporation of the Company and the Restated Bylaws of the Company, in each case as currently in effect, and as certified by the Secretary of the Company on the date hereof as being true, complete and correct and in full force and effect.  We have also examined originals, or copies of originals certified or otherwise identified to our satisfaction, of such records of the Company, agreements, documents, certificates and other statements of governmental officials and other instruments, and have examined such questions of law and have satisfied ourselves as to such matters of fact, as we have considered relevant and necessary as a basis for the opinion expressed below.  We have assumed the authenticity of all documents submitted to us as originals, the genuineness of all signatures, the legal capacity of all persons and the conformity with the original documents of any copies thereof submitted to us for examination.  We have also assumed that the Indenture is the valid and legally binding obligation of the Trustee.

Based on the foregoing, and subject to the qualifications and limitations set forth herein, it is our opinion that the issuance and sale of the Securities pursuant to the Underwriting Agreement have been duly authorized by the Company and, when the Securities are duly executed and delivered by the Company, and duly authenticated by the Trustee, all in accordance with the provisions of the Indenture, and duly delivered to the purchasers thereof against payment of the agreed consideration therefor as contemplated by the Underwriting Agreement, the Securities will constitute valid and legally binding obligations of the Company.

Our opinion above is subject to bankruptcy, insolvency, reorganization, moratorium, fraudulent conveyance, fraudulent transfer and other similar laws relating to or affecting creditors’ rights generally, and to general equitable principles (regardless of whether considered in a proceeding in equity or at law), including concepts of commercial reasonableness, good faith and fair dealing and the possible unavailability of specific performance or injunctive relief.

This opinion letter is limited to the General Corporation Law of the State of Delaware, the laws of the State of Illinois and the federal laws of the United States of America (excluding the Federal Communications Act of 1934, as amended, and any rules and regulations in effect thereunder) to the extent applicable.

2

The following persons are members of our firm:  Walter C.D. Carlson, a trustee and beneficiary of a voting trust that controls the Company, the non-executive chairman of the board and member of the board of directors of the Company and a director of a subsidiary of the Company; William S. DeCarlo, the General Counsel of the Company and an Assistant Secretary of the Company and certain subsidiaries of the Company; and Stephen P. Fitzell, the General Counsel and/or an Assistant Secretary of certain subsidiaries of the Company.

We hereby consent to the filing of this opinion letter as an exhibit to the Company’s Current Report on Form 8-K on the date hereof, which Form 8-K will be incorporated by reference into the Registration Statement, and to all references to our firm included or made a part of the Registration Statement.  In giving such consent, we do not thereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act or the related rules promulgated by the Commission.

3