Exhibit 5.1

March 15, 2021 Mayer Brown LLP 71 South Wacker Drive
Chicago, Illinois 60606-4637   Main Tel +1 312 782 0600
Main Fax +1 312 701 7711 www.mayerbrown.com

Potbelly Corporation

111 N. Canal Street

Chicago, Illinois 60606

Ladies and Gentlemen:

We have acted as counsel to Potbelly Corporation, a Delaware corporation (the “Company”) in connection with the preparation of a shelf registration statement on Form S-3 (the “Registration Statement”), to be filed by the Company with the Securities and Exchange Commission (the “Commission”) on the date hereof under the Securities Act of 1933, as amended (the “Act”). The Registration Statement relates to the offer and sale by the selling stockholders named in the Registration Statement (the “Selling Stockholders”) of (i) 3,249,668 shares (the “Outstanding Shares”) of the Company’s common stock, par value $0.01 per share, (the “Common Stock”) and (ii) 1,299, 861 shares (the “Warrant Shares” and, together with the Outstanding Shares, the “Shares”) of Common Stock issuable upon exercise of warrants (the “Warrants”) issued to the Selling Stockholders pursuant to the Securities Purchase Agreement (defined below).

The Company is registering the Shares pursuant to its obligations under the registration rights agreement, dated as of February 14, 2021 (the “Registration Rights Agreement”), between the Company and the Selling Stockholders. The Outstanding Shares and the Warrant were issued to the Selling Stockholders pursuant to the securities purchase agreement, dated February 11, 2021 (the “Investment Agreement” and together with the Registration Rights Agreement, the “Transaction Documents”).

This opinion is being delivered in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Act. Capitalized terms used but not otherwise defined herein have the meanings ascribed to them in the Registration Statement.

In rendering the opinions expressed herein, we have examined (i) the Transaction Documents; (ii) the Seventh Amended and Restated Certificate of Incorporation of the Company and all amendments thereto; (iii) the Amended and Restated Bylaws of the Company and all amendments thereto; (iv) resolutions of the board of directors of the Company relating to the issuance of the Shares and the Warrants. We have also examined such other documents and instruments and have made such further investigations as we have deemed necessary or appropriate in connection with this opinion.

In expressing the opinions set forth below, we have assumed the genuineness of all signatures, the conformity to the originals of all documents reviewed by us as copies, the authenticity and completeness of all original documents reviewed by us in original or copy form and the legal competence of each individual executing any document. As to all parties other than the Company, we have assumed the due authorization, execution and delivery of all documents and the validity and enforceability thereof against all parties thereto in accordance with their respective terms.

Mayer Brown is a global services provider comprising an association of legal practices that are separate entities including

Mayer Brown LLP (Illinois, USA), Mayer Brown International LLP (England), Mayer Brown (a Hong Kong partnership)

and Tauil & Chequer Advogados (a Brazilian partnership).

Mayer Brown LLP

March 15, 2021

Page 2

With respect to our opinion set forth below, we have assumed that (i) the Company received the consideration for the Outstanding Shares and the Warrants set forth in the Securities Purchase Agreement and the applicable board resolutions and (ii) the issuance of the Outstanding Shares has been registered in the Company’s stock registry. As to any facts relevant to the opinion stated herein that we did not independently establish or verify, we have relied upon statements and representations of officers and other representatives of the Company and the Selling Stockholders and others and of public officials, including the factual representations and warranties set forth in the Securities Purchase Agreement.

Based upon and subject to the foregoing, and having regard for legal considerations which we deem relevant, we are of the opinion that:

(i) the Outstanding Shares have been duly authorized and validly issued and are fully paid and non-assessable; and

(ii) the Warrant Shares have been duly authorized and reserved for issuance upon exercise and, upon exercise of the Warrants, payment of the exercise price thereof and issuance and delivery in accordance with the terms of the Warrants, will be validly issued, fully paid and non-assessable.

This opinion is limited to matters governed by the Federal laws of the United States of America, the laws of the State of New York and the General Corporation Law of the State of Delaware (including the applicable provisions of the Delaware Constitution and the reported judicial decisions interpreting the General Corporation Law of the State of Delaware and such applicable provisions of the Delaware Constitution).

The opinions and statements expressed herein are as of the date hereof. We assume no obligation to update or supplement this opinion letter to reflect any facts or circumstances that may hereafter come to our attention or any changes in applicable law which may hereafter occur.

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the reference to our name under the caption “Legal Matters” in the prospectus. In giving such consent, we do not thereby admit that we are in the category of persons whose consent is required under Section 7 of the Act.

Very truly yours,

MAYER BROWN LLP

ESB:

2