Exhibit 10.1

FIRST AMENDMENT OF

EXECUTIVE EMPLOYMENT AGREEMENT

WHEREAS, Potbelly Corporation, a Delaware corporation (hereinafter referred to as “Company”), and Alan Johnson, an individual (hereinafter referred to as “Executive”), are parties to that certain Executive Employment Agreement entered into as of November 29, 2017 (the “Agreement”);

WHEREAS, Company and Executive have determined that it is appropriate to amend the Agreement to reflect certain changes agreed by Company and Executive with respect to Executive’s equity-based compensation; and

NOW, THEREFORE, in consideration of the promises set forth herein and other good and valuable consideration, the Agreement is hereby amended, effective as of May 14, 2018, as follows:

“(c) Equity Compensation. As of the Effective Date, as an initial grant under the Equity Plan (and not to be considered representative of any future grants either as to amount or form), Executive was granted an equity award with a value of $2,000,000, which equity award grant was comprised of restricted stock units having an approximate value of $1,000,000 and stock options (the ‘Initial Option Grant’) with respect to 200,401 shares of Company common stock and with an exercise price of $12.800 per share, which Initial Option Grant had an approximate Black-Scholes value of $1,000,000. As of May 14, 2018, with Executive’s consent, the Initial Option Grant was amended to provide for an exercise price of $14.08 and Executive acknowledges and agrees that such amendment to the Initial Option Grant does not constitute a material breach of the Agreement or any other basis for Executive to terminate his employment with Company for Good Reason. Executive shall not be entitled to any grants of awards under Equity Plan in calendar year 2018. For years after 2018, Executive shall be eligible to participate in the Equity Plan with an annual target award value of $1,000,000, which equity award may in the form of stock options, restricted stock units (including performance-based restricted stock units) and/or other forms of awards permitted under the Equity Plan, as determined in the sole discretion of the Compensation Committee; provided, however, that the actual value of the equity award for any year shall be determined by the Compensation Committee in its sole discretion taking into account Executive’s performance and performance of Company for the applicable period to which the award relates. All awards under the Equity Plan shall be evidenced by an award agreement setting forth the terms and conditions of the applicable award. For purposes of determining the value of any equity award made under the Equity Plan in accordance with this paragraph (c), the value of stock options granted shall be determined based on the Black-Scholes valuation method.”

[SIGNATURE PAGE FOLLOWS]

IN WITNESS WHEREOF, each party has caused this First Amendment of Executive Employment Agreement to be executed in a manner appropriate for such party, all effective as of May 14, 2018.

2