Exhibit 5.1

Mayer Brown LLP

71 South Wacker Drive

Chicago, IL 60606

United States of America

T: +1 312 782 0600

F: +1 312 701 7711

mayerbrown.com

June 10, 2019

Potbelly Corporation

111 North Canal Street, Suite 850

Chicago, Illinois 60606

Re: Registration Statement on Form S-8

Ladies and Gentlemen:

We have acted as counsel to Potbelly Corporation, a Delaware corporation (the “Company”), in connection with the Post-Effective Amendment No. 1 to Registration Statement on Form S-8 (the “Post-Effective Amendment”) relating to the registration under the Securities Act of 1933, as amended (the “Securities Act”) of up to 2,288,971 shares of the Company’s common stock, par value $0.01 per share (the “Shares”), issuable pursuant to the Company’s 2019 Long-Term Incentive Plan (the “2019 Plan”), such Shares having originally been authorized for issuance pursuant to the Company’s Amended and Restated 2013 Long-Term Incentive Plan, as further explained in the “Explanatory Note” to the Post-Effective Amendment.

As counsel to the Company, we have examined the Company’s amended and restated certificate of incorporation, amended and restated bylaws and resolutions of the board of directors and stockholders of the Company. 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 opinion 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 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.

Based upon and subject to the foregoing, and having regard for legal considerations which we deem relevant, we are of the opinion that the Shares have been duly authorized and, when issued and sold in accordance with the 2019 Plan, 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. 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 Securities and Exchange Commission thereunder.

Very truly yours,

/s/ Mayer Brown LLP

Mayer Brown LLP

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).