Exhibit 5.1

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

September 30, 2013

Potbelly Corporation

222 Merchandise Mart Plaza, 23rd Floor

Chicago, Illinois 60654

Re: Registration Statement on Form S-1

Ladies and Gentlemen:

We have acted as counsel to Potbelly Corporation, a Delaware corporation (the “Company”), in connection with the registration statement on Form S-1 filed by the Company with the Securities and Exchange Commission (the “Commission”) on August 29, 2013 (File No. 333-190893), as amended (the “Registration Statement”), under the Securities Act of 1933, as amended (the “Securities Act”). The Registration Statement relates to the offer and sale of 8,625,000 shares of common stock of the Company, $0.01 par value per share (the “Shares”), including (i) shares that will be offered and may be sold by the Company (including shares issuable upon exercise of an over-allotment option granted by the Company) (the “Primary Shares”), (ii) shares that are presently issued and outstanding and that will be offered and may be sold by certain stockholders of the Company (the “Secondary Shares”) and (iii) shares that are not presently issued or outstanding but are issuable upon the cashless exercise of outstanding stock options and that will be offered and may be sold by certain stockholders of the Company (the “Other Secondary Shares”). This opinion is being furnished in connection with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act, and no opinion is expressed herein as to any matter pertaining to the contents of the Registration Statement or related prospectus (the “Prospectus”), other than as expressly stated herein.

As counsel to the Company, we have examined (i) the Registration Statement; (ii) the Seventh Amended and Restated Certificate of Incorporation (the “Restated Certificate of Incorporation”) of the Company in the form filed as Exhibit 3.1 to the Registration Statement, to be filed with the Secretary of State of the State of Delaware prior to the issuance of the Shares; (iii) the Second Amended and Restated By-laws of the Company in the form filed as Exhibit 3.2 to the Registration Statement; (iv) the form of underwriting agreement (the “Underwriting Agreement”) filed as Exhibit 1.1 to the Registration Statement; and (v) resolutions of the board of directors and stockholders of the Company relating to the offering of the Shares. 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. We have also assumed that (i) the Registration Statement will become and remain effective under the Securities Act and (ii) all of the Shares will be issued and sold in compliance with applicable federal and state securities or blue sky laws and in the manner stated in the Registration Statement.

As to matters of fact (but not as to legal conclusions), to the extent we deemed proper, we have relied on certificates of responsible officers of the Company and of public officials.

Mayer Brown LLP operates in combination with other Mayer Brown entities with offices in Europe and Asia

and is associated with Tauil & Chequer Advogados, a Brazilian law partnership.

Mayer Brown LLP

September 30, 2013

Page 2

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

1. Assuming the Company files its Restated Certificate of Incorporation with the Secretary of State of the State of Delaware, the Primary Shares, when issued and delivered against payment therefor in the circumstances contemplated by the Underwriting Agreement, will be validly issued, fully paid and non-assessable;

2. The Secondary Shares are validly issued, fully paid and non-assessable; and

3. The Other Secondary Shares, when issued, sold and delivered upon the terms of the option agreements governing such options, will be validly issued, fully paid and non-assessable.

The opinion expressed above is limited to the Delaware General Corporation Law and we express no opinion with respect to any other laws.

We consent to your filing this opinion as an exhibit to the Registration Statement and to the reference to our firm in the Prospectus under the heading “Legal Matters.” 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 Securities Act or the rules and regulations of the Commission thereunder.

Very truly yours,

/s/ Mayer Brown LLP

Mayer Brown LLP