AMENDMENT NO. 1 TO CREDIT AGREEMENT

Exhibit 10.4

AMENDMENT NO. 1

TO

CREDIT AGREEMENT

THIS AMENDMENT NO. 1 TO CREDIT AGREEMENT (this “Amendment”) is entered into as of April 26, 2013 among POTBELLY SANDWICH WORKS, LLC, an Illinois limited liability company (“Borrower”), the other Loan Parties (as such term is defined in the Credit Agreement), the financial institutions listed on the signature pages hereto as lenders (the “Lenders”), and JPMORGAN CHASE BANK, N.A., as administrative agent for the Lenders (in such capacity, the “Administrative Agent”).

W I T N E S S E T H:

WHEREAS, the Loan Parties, the Lenders and the Administrative Agent have entered into that certain Credit Agreement dated as of September 21, 2012 (as amended, supplemented or otherwise modified from time to time, the “Credit Agreement”); and

WHEREAS, the Loan Parties desire to amend the Credit Agreement as set forth herein, and the Administrative Agent and the Lenders are willing to do so on the terms and subject to the conditions set forth herein;

NOW, THEREFORE, in consideration of the premises set forth above, the terms and conditions contained herein, and for other good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, the parties hereto agree as follows:

1. Definitions. Terms defined in the Credit Agreement that are used herein shall have the same meanings as are set forth in the Credit Agreement for such terms unless otherwise defined herein.

2. Amendment to Credit Agreement. Upon the occurrence of the Effective Time (as hereinafter defined), the Credit Agreement is hereby amended as follows:

(a) Section 5.01 of the Credit Agreement is hereby amended by inserting after the phrase “within 120 days after the end of each Fiscal Year of the Borrower” and before the comma appearing thereafter the following:

(provided that such period shall be 151 days in the case of the Fiscal Year ending December 30, 2012)

3. Conditions. When each of the following conditions has been completely satisfied as determined by the Administrative Agent in its reasonable discretion, the amendments set forth in Section 2 of this Amendment shall become effective (the time of such satisfaction being hereinafter referred to as the “Effective Time;” the Effective Time shall be deemed to occur on the date of this Amendment (the “Effective Date”) unless the Administrative Agent provides written notice to the contrary to the Loan Parties):

(a) Documents. The Administrative Agent shall have received each of the following agreements, instruments and other documents, in each case in form and substance reasonably satisfactory to the Administrative Agent:

(i) this Amendment duly executed and delivered by the Loan Parties, the Lenders and the Administrative Agent;

(ii) the documents, instruments, agreements, opinions, certificates and other items listed on the Document Checklist attached hereto as Exhibit A; and

(iii) such other documents, agreements, instruments, certificates, opinions and other items as the Administrative Agent may reasonably request in connection with this Amendment.

(b) Representations and Warranties; No Default. As of the date hereof (and, if different, also as of the Effective Date): (a) the representations and warranties contained herein, in the Credit Agreement and in each other Loan Document shall be true and correct in all material respects (both immediately before and after giving effect to consummation of the transactions contemplated hereby), except to the extent any such representation and warranty expressly refers to an earlier date, in which case such representation and warranty shall be true and correct in all material respects as of such earlier date; and (b) no Default or Event of Default shall exist.

(c) Proceedings. All resolutions, consents and other corporate or limited liability company proceedings taken or to be taken in connection with the transactions contemplated hereby, and all agreements, instruments, certificates and other documents relating thereto, shall be in form and substance satisfactory to the Administrative Agent, as determined in its sole and absolute discretion, and shall be in full force and effect.

(d) Fees. All out-of-pocket expenses required to be paid to the Administrative Agent’s special counsel on or prior to the Effective Date shall have been paid in full.

4. Representations and Warranties of the Loan Parties. Each Loan Party represents and warrants that: (a) the execution and delivery by such Loan Party of this Amendment, each other document, instrument and agreement to be executed and delivered by such Loan Party in connection herewith (this Amendment and such other documents, instruments and agreements are referred to herein, collectively, as the “Amendment Documents”) and the Credit Agreement (as amended hereby) and the performance of such Loan Party’s obligations hereunder and thereunder: (i) are within the corporate or limited liability company powers of such Loan Party, (ii) are duly authorized by the board of directors or managers of such Loan Party, and, if necessary, the shareholders or members of such Loan Party, (iii) are not in contravention of the terms of such Loan Party’s articles or certificate of incorporation or formation, by-laws, operating, management or partnership agreement or other organizational documents, (iv) are not in contravention of the terms of the provisions of any indenture, instrument or agreement to which such Loan Party is a party or is subject, or by which it, or its property, is bound, or conflict with or constitute a default thereunder, or result in, or require, the creation or imposition of any Lien in, of or on the property of such Loan Party pursuant to the

-2-

terms of any such indenture, instrument or agreement (other than Liens in favor of the Administrative Agent, for the benefit of itself and the Lenders, under the Security Agreement and any other Permitted Encumbrances), (v) do not contravene any law, rule, regulation, order, writ, judgment, injunction, decree or award binding on such Loan Party; and (vi) do not require any order, consent, adjudication, approval, license, authorization, or validation of, or filing, recording or registration with, or exemption by, or other action in respect of any governmental or public body or authority, or any subdivision thereof; (b) each of this Amendment and the other Amendment Documents has been duly executed and delivered by such Loan Party and constitutes the legal, valid and binding obligation of such Loan Party, enforceable against such Loan Party in accordance with its terms, except as limited by applicable bankruptcy, reorganization, insolvency or similar laws affecting the enforcement of creditors’ rights generally and except as limited by general principles of equity; (c) the Credit Agreement, and each other Loan Document, after giving effect hereto, constitutes the legal, valid and binding obligation of such Loan Party, enforceable against such Loan Party in accordance with its terms, except as enforcement may be limited by bankruptcy, insolvency, reorganization or other similar laws affecting the enforcement of creditors’ rights generally or by general equitable principles; (d) as of the date hereof, and (after giving effect hereto and consummation of the transactions contemplated hereby) as of the Effective Date, there exists no Default or Event of Default; and (e) all conditions set forth in Section 3 of this Amendment have been satisfied in full (provided that no representation or warranty is made as to the Administrative Agent’s or any Lender’s acceptance or satisfaction with any matter). All representations and warranties contained in this Amendment shall survive the execution and delivery of this Amendment.

5. Consent of Loan Guarantor. Each Loan Party (other than Borrower), in its capacity as a Loan Guarantor under

Article X of the Credit Agreement, hereby consents to this Amendment and the amendments contained herein and confirms and agrees that, notwithstanding this Amendment and the effectiveness of the amendments contained herein, the Loan Guaranty is, and shall continue to be, in full force and effect and is hereby confirmed and ratified in all respects notwithstanding the terms of this Amendment or any other amendment to the Credit Agreement. Nothing herein is intended or shall be deemed to limit the Administrative Agent’s or any Lender’s rights under the Loan Guaranty to take actions without the consent of any Loan Guarantor.

6. Reference to/Effect on the Credit Agreement, Etc.

(a) On and after the Effective Date: (i) each reference in the Credit Agreement to “this Agreement,” “hereunder,” “hereof,” “herein,” or words of like import shall mean and be a reference to the Credit Agreement, as amended hereby, and (ii) each reference to the Credit Agreement in all other Loan Documents shall mean and be a reference to the Credit Agreement, as amended hereby.

(b) Except as otherwise provided herein, the Credit Agreement, all other Loan Document, all covenants, representations and warranties made therein, and all other documents, instruments and agreements executed and/or delivered in connection therewith, shall remain in full force and effect, and are hereby reaffirmed, ratified and confirmed.

-3-

(c) The execution, delivery and effectiveness of this Amendment and the other Amendment Documents shall not (i) except as specifically stated herein, amend the Credit Agreement or any other Loan Document, (ii) operate as a waiver of any right, power or remedy of the Administrative Agent or any Lender, or (iii) constitute a waiver of, or consent to any departure from, any provision of the Credit Agreement or any other Loan Document or any other documents, instruments and agreements executed or delivered in connection therewith.

(d) Each Loan Party acknowledges and agrees that: (i) as of the date hereof (and, if different, also as of the Effective Date), such Loan Party has no defenses, claims or set-offs to the payment of the Secured Obligations or to the enforcement of the Secured Obligations, the Credit Agreement or any of the other Loan Documents; and (ii) the Liens granted to the Administrative Agent, for the benefit of itself and the Lenders, by such Loan Party are and remain valid perfected Liens in the assets of such Loan Party securing the payment and performance of the Secured Obligations.

(e) Borrower agrees to deliver to the Administrative Agent and each Lender a draft of its audited financial statements and a draft Compliance Certificate by April 30, 2013 in compliance with Sections 5.1(a) and 5.1(b) before giving effect to this Amendment, respectively, except for their status as drafts, pending final audit review.

(f) This Amendment and the other Amendment Documents shall each be deemed a Loan Document for the purposes of the Credit Agreement.

7. Miscellaneous.

(a) Choice of Law. This Amendment shall be governed by and construed in accordance with the internal laws (including, without limitation, 735 ILCS Section 105/5-1 et seq., but otherwise without regard to the conflict of laws provisions) of the State of Illinois, but giving effect to federal laws applicable to national banks.

(b) Severability. Any provision of any Amendment Document held to be invalid, illegal or unenforceable in any jurisdiction shall, as to such jurisdiction, be ineffective to the extent of such invalidity, illegality or unenforceability without affecting the validity, legality and enforceability of the remaining provisions thereof; and the invalidity of a particular provision in a particular jurisdiction shall not invalidate such provision in any other jurisdiction.

(c) WAIVER OF JURY TRIAL. EACH PARTY HERETO HEREBY WAIVES, TO THE FULLEST EXTENT PERMITTED BY APPLICABLE LAW, ANY RIGHT IT MAY HAVE TO A TRIAL BY JURY IN ANY LEGAL PROCEEDING DIRECTLY OR INDIRECTLY ARISING OUT OF OR RELATING TO THIS AMENDMENT, ANY OTHER AMENDMENT DOCUMENT OR THE TRANSACTIONS CONTEMPLATED THEREBY (WHETHER BASED ON CONTRACT, TORT OR ANY OTHER THEORY). EACH PARTY HERETO (A) CERTIFIES THAT NO REPRESENTATIVE, AGENT OR ATTORNEY OF ANY OTHER PARTY HAS REPRESENTED, EXPRESSLY OR OTHERWISE, THAT SUCH OTHER PARTY WOULD NOT, IN THE EVENT OF LITIGATION, SEEK TO ENFORCE THE FOREGOING WAIVER AND (B) ACKNOWLEDGES THAT IT AND THE OTHER PARTIES HERETO HAVE BEEN INDUCED TO ENTER INTO THIS AGREEMENT BY, AMONG OTHER THINGS, THE MUTUAL WAIVERS AND CERTIFICATIONS IN THIS SECTION.

-4-

(d) Headings. Section headings used herein are for convenience of reference only, are not part of this Amendment and shall not affect the construction of, or be taken into consideration in interpreting, this Amendment.

(e) Counterparts. This Amendment may be executed and accepted in any number of counterparts (and by different parties hereto on different counterparts), each of which shall constitute an original, but all of which when taken together shall constitute a single contract. Delivery of an executed counterpart of a signature page of this Amendment by facsimile or other electronic transmission shall be effective as delivery of a manually executed counterpart of this Amendment.

[signature page(s) follow]

-5-

IN WITNESS WHEREOF, this Amendment No. 1 to Credit Agreement has been duly executed as of the day and year first above written.

2

EXHIBIT A

Document Checklist

See Attached

AMENDMENT NO. 1

TO CREDIT AGREEMENT

among

POTBELLY SANDWICH WORKS, LLC,

as Borrower and as a Loan Party

THE OTHER LOAN PARTIES PARTY THERETO,

THE LENDERS PARTY THERETO

and

JPMORGAN CHASE BANK, N.A.,

as Administrative Agent

April 26, 2013

DOCUMENT CHECKLIST

Definitions

Administrative Agent JPMorgan Chase Bank, N.A.

Lender JPMorgan Chase Bank, N.A. (“Chase”)