Exhibit 5.1

[LETTERHEAD OF GIBSON, DUNN & CRUTCHER LLP]

May 25, 2018

Noodles & Company

520 Zang Street, Suite D

Broomfield, CO 80021

Re:Noodles & Company

Registration Statement on Form S‑3

Ladies and Gentlemen:

We have examined the Registration Statement on Form S-3 (the “Registration Statement”), of Noodles & Company, a Delaware corporation (the “Company”), filed with the Securities and Exchange Commission (the “Commission”) pursuant to the Securities Act of 1933, as amended (the “Securities Act”), in connection with the offering by the Company of up to 5,000,000 shares (the “Company Shares”) of the Company’s Class A common stock, par value $0.01 per share (the “Class A Common Stock”), and by the stockholders listed in the Registration Statement (the “Selling Stockholders”) of up to an aggregate of 30,207,509 shares (the “Selling Stockholders Shares,” and together with the Company Shares, the “Shares”) of the Company’s Class A Common Stock, consisting of (i) outstanding shares of Class A Common Stock (the “Outstanding Shares”) and (ii) shares of Class A Common Stock issuable upon the exercise (the “Exercise Shares”) of warrants to purchase Class A Common Stock (the “Warrants”).

In arriving at the opinion expressed below, we have examined originals, or copies certified or otherwise identified to our satisfaction as being true and complete copies of the originals, of specimen Class A Common Stock certificates, the Warrants and such other documents, corporate records, certificates of officers of the Company and of public officials and other instruments as we have deemed necessary or advisable to enable us to render the opinions set forth below. In our examination, we have assumed without independent investigation the genuineness of all signatures, the legal capacity and competency of all natural persons, the authenticity of all documents submitted to us as originals and the conformity to original documents of all documents submitted to us as copies.

We have assumed that (i) at the time any Shares are sold pursuant to the Registration Statement (the “Relevant Time”), the Registration Statement and any supplements and amendments thereto (including post-effective amendments) will be effective and will comply with all applicable laws; (ii) if required, at the Relevant Time, a prospectus supplement will have been prepared and filed with the Commission describing the Shares offered thereby and all related documentation and will comply with all applicable laws; (iii) all Shares will be offered and sold in the manner stated in the Registration Statement and, if required, any applicable prospectus supplement; (iv) at the Relevant Time, all corporate or other action required to be taken by the Company to duly authorize each proposed issuance of Company Shares and any related documentation (including (a) the due reservation of any shares of Common Stock for issuance upon exercise, conversion or exchange of any Warrants for Common Stock, and (b) the execution (in the case of certificated Shares) and delivery of the Shares and any related documentation) shall have been duly completed and shall remain in full force and

1

effect; (v) at the Relevant Time, upon exercise of the Warrants, the total number of shares of Class A Common Stock issued and outstanding will not exceed the total number of shares of Class A Common Stock that the Company is then authorized to issue under its amended and restated certificate of incorporation and other relevant documents; and (vi) at the Relevant Time, a definitive purchase, underwriting or similar agreement and any other necessary agreement with respect to any Shares offered or issued will have been duly authorized by all necessary corporate or other action of the Company and duly executed and delivered by the Company and the other parties thereto.

Based upon the foregoing, and subject to the assumptions, exceptions, qualifications and limitations set forth herein, we are of the opinion that (i) when the Company Shares have been duly executed (in the case of certificated shares) and delivered in accordance with the applicable definitive purchase, underwriting or similar agreement for the consideration provided for therein, which consideration, on a per-share basis, shall not be less than the par value of the Company Shares, (ii) the Outstanding Shares are validly issued, fully paid and non-assessable, and (iii) the Exercise Shares will be, when issued upon the exercise of the Warrants in accordance with the terms thereof, validly issued, fully paid and non-assessable.

This opinion is limited to the effect of the current state of the Delaware General Corporation Law and the facts as they current exist. We are not admitted to practice in the State of Delaware; however, we are generally familiar with the Delaware General Corporation Law as currently in effect and have made such inquiries as we consider necessary to render the opinion above. We assume no obligation to revise or supplement this opinion in the event of future changes in such laws or the interpretation thereof or such facts.

We consent to the filing of this opinion as an exhibit to the Registration Statement, and we further consent to the use of our name under the caption “Validity of the Class A Common Stock” in the Registration Statement and the prospectus that forms a part thereof. In giving these consents, we do not thereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act or the Rules and Regulations of the Commission.

Very truly yours,

/s/ Gibson, Dunn & Crutcher LLP

2