REGISTRATION RIGHTS AGREEMENT

Exhibit 4.1

REGISTRATION RIGHTS AGREEMENT

THIS REGISTRATION RIGHTS AGREEMENT (this “Agreement”), made and entered into as of July 21, 2012, by and among the parties named on the signature page hereto (collectively referred to hereinafter as the “Holders”) and Flowers Foods, Inc., a Georgia corporation (the “Company”);

WHEREAS, the Holders are parties to an Agreement and Plan of Merger dated May 31, 2012 by and among the Company, LobsterCo II, LLC, Aarow Leasing, Inc., The Everest Company, Incorporated and the shareholders named therein (“Merger Agreement”);

WHEREAS, pursuant to the Merger Agreement, the Holders will acquire shares of the Company’s common stock (the “Common Stock”);

WHEREAS, the Holders have agreed to certain restrictions on sale of the Common Stock pursuant to the terms of the Merger Agreement; and

WHEREAS, in connection with the Merger Agreement, the Company has agreed to provide the registration rights provided in this Agreement;

NOW, THEREFORE, in consideration of the premises and for other good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, the parties hereto do agree to enter into the agreements contained hereinbelow as follows:

1. REGISTRATION RIGHTS.

1.1 Certain Definitions. As used in this Agreement, in addition to the terms defined elsewhere in this Agreement, the following terms shall have the following respective meanings:

“Business Day” means any day other than a day on which the SEC or the office of the Delaware Secretary of State is closed.

“Deferral Notice” has the meaning specified in Section 1.4(d).

“Effectiveness Period” means the period that is twelve (12) months from the date the Registration Statement is declared effective by the SEC (exclusive of any period during which Holders are prohibited or impaired from selling Registrable Securities solely as a result of the suspension of availability of the Registration Statement pursuant to Section 1.4(d)), provided however, that if at the date that the Effectiveness Period would otherwise terminate, a Holder is deemed to be an “affiliate” of the Company as defined in Rule 144 of the Securities Act, then the Effectiveness Period shall be extended until such time as the Holder is no longer deemed to be such an “affiliate.”.

“Permitted Transferees” means any charitable or private foundation on whose board the Holder serves.

“Prospectus” means the prospectus included in any Registration Statement (including, without limitation, a prospectus that discloses information previously omitted from a prospectus

filed as part of an effective registration statement in reliance upon Rule 415 promulgated under the Securities Act), as amended or supplemented by any amendment or prospectus supplement, including post-effective amendments, and all materials incorporated by reference or explicitly deemed to be incorporated by reference in such Prospectus.

“Registrable Securities” means all shares of Common Stock held by the Holders, together with any shares of Common Stock issued with respect thereto upon any stock split, stock dividend, recapitalization or similar event; provided, however, that any such shares of Common Stock shall cease to be Registrable Securities (i) when they have been sold pursuant to a Registration Statement, (ii) with respect to any Holder, at such time as the entire amount of such Holder’s Registrable Securities may be sold pursuant to Rule 144 without being subject to any volume limitations, (iii) have been transferred to someone other than a Holder, or (iv) have ceased to be outstanding.

“Registration Expenses” means all expenses incurred by the Company in complying with Section 1.2 hereof, including, without limitation, all registration and filing fees, printing expenses, fees and disbursements of counsel for the Company, state “blue sky” fees and expenses, and accountants’ expenses but excluding any commissions or other fees of any broker, dealer or underwriter incurred in connection with a sale of Registrable Securities and any taxes applicable to any Holder with respect to any transfer or sale of Registrable Securities.

“Registration Statement” has the meaning specified in Section 1.2.

“SEC” means the U.S. Securities and Exchange Commission.

“Securities Act” shall mean the Securities Act of 1933 and the rules and regulations promulgated by the SEC thereunder.

“Securities Exchange Act” shall mean the Securities Exchange Act of 1934 and the rules and regulations promulgated by the SEC thereunder.

1.2 Company Registration. The Company shall prepare and file or cause to be prepared and filed with the SEC, no later than fifteen (15) days after the date of this Agreement, a Registration Statement for an offering to be made on a delayed or continuous basis pursuant to Rule 415 of the Securities Act registering the resale from time to time by Holders of all of the Registrable Securities held by the Holders (the “Registration Statement”). The Registration Statement shall be on Form S-3 ASR or another appropriate form permitting registration of such Registrable Securities for resale by such Holders. The Company shall use commercially reasonable efforts to cause the Registration Statement to be declared effective under the Securities Act as soon as practicable and to keep the Registration Statement effective under the Securities Act until the expiration of the Effectiveness Period.

1.3 Expenses of Registration. All Registration Expenses incurred in connection with the performance of the Company’s obligations under Section 1.2 shall be borne by the Company (but excluding any fees of counsel for the Holders, which shall be paid by the Holders).

- 2 -

1.4 Registration Procedures. The Company shall keep each Holder advised in writing as to the initial filing and the effectiveness of the Registration Statement, and as to any issuances of stop orders, injunctions or other instructions to suspend the use thereof. At its expense the Company shall use its reasonable best efforts to:

(a) upon written request, before filing any Registration Statement or Prospectus or any amendments or supplements thereto with the SEC, furnish to the Holders copies of all such documents proposed to be filed and use reasonable efforts to reflect in each such document when so filed with the SEC such comments as the Holders reasonably shall propose within one Business Day of the delivery of such copies to the Holders;

(b) subject to Section 1.4(d), prepare and file with the SEC such amendments and post-effective amendments to each Registration Statement as may be necessary to keep such Registration Statement continuously effective for the Effectiveness Period; cause the related Prospectus to be supplemented by any required Prospectus supplement, and as so supplemented to be filed pursuant to Rule 424 (or any similar provisions then in force) under the Securities Act; and use reasonable efforts to comply with the provisions of the Securities Act applicable to it; and

(c) (i) as promptly as reasonably practicable, but within three Business Days in any event, give notice to the Holders (A) when any Prospectus, Prospectus supplement, Registration Statement or post-effective amendment to a Registration Statement has been filed with the SEC and, with respect to a Registration Statement or any post-effective amendment, when the same has been declared effective (provided, however, that the Company shall not be required by this clause (A) to notify the Holders of the filing of a Prospectus supplement that does nothing more substantive than name one or more Holders as selling security holders), (B) of any request, following the effectiveness of a Registration Statement under the Securities Act, by the SEC or any other federal or state governmental authority for amendments or supplements to such Registration Statement or related Prospectus or for additional information,

(ii) give notice to the Holders within one Business Day following notice to the Company (A) of the issuance by the SEC or any other federal or state governmental authority of any stop order or injunction suspending or enjoining the use of any Prospectus or the effectiveness of a Registration Statement or the initiation or threatening of any proceedings for that purpose, (B) of the receipt by the Company of any notification with respect to the suspension of the qualification or exemption from qualification of any of the Registrable Securities for sale in any jurisdiction or the initiation or threatening of any proceeding for such purpose, and (C) of the happening of any event that makes any statement made in a Registration Statement or the related Prospectus untrue in any material respect or that requires changes in order to make the statements therein not misleading;

(d) (i) subject to the last sentence in this Section 1.4(d), upon the occurrence of any event contemplated by Section 1.4(c)(ii)(C), but within fifteen (15) Business Days, prepare and file a post-effective amendment to such Registration Statement or a supplement to the related Prospectus or any document incorporated therein by reference, or file any other required document that would be incorporated by reference into such Registration Statement and Prospectus, so that such Registration Statement does not contain any untrue

- 3 -

statement of a material fact or omit to state any material fact required to be stated therein or necessary to make the statements therein not misleading, and that such Prospectus does not contain any untrue statement of a material fact or omit to state any material fact required to be stated therein or necessary to make the statements therein, in light of the circumstances under which they were made, not misleading, and, in the case of a post-effective amendment to a Registration Statement, subject to the next sentence, use commercially reasonable efforts to cause it to be declared effective as promptly as is reasonably practicable, and give notice to the Holders listed as selling security holders in such Prospectus that the availability of the Registration Statement is suspended (a “Deferral Notice”) and, upon receipt of any Deferral Notice, each such Holder agrees not to sell any Registrable Securities pursuant to the Registration Statement until such Holder’s receipt of copies of the supplemented or amended Prospectus or until it is advised in writing by the Company that the Prospectus may be used, and has received copies of any additional or supplemental filings that are incorporated or deemed incorporated by reference in such Prospectus. The Company shall use its reasonable best efforts to ensure that the use of the Prospectus may be resumed as promptly as is practicable, except that if in the good faith judgment of the Company public disclosure of a material fact or event would be prejudicial to or contrary to the interests of the Company, the Company may delay such action for so long as reasonably practicable and until such suspension is no longer appropriate.

1.5 Indemnification.

(a) The Company agrees to indemnify and hold harmless the Holders and each person, if any, who controls the Holders within the meaning of either Section 15 of the Securities Act or Section 20 of the Exchange Act, as follows:

(i) against any and all loss, liability, claim, damage and expense whatsoever, as incurred, arising out of any untrue statement or alleged untrue statement of a material fact contained in the Registration Statement (or any amendment thereto), or the omission or alleged omission therefrom of a material fact required to be stated therein or necessary in order to make the statements therein, in light of the circumstances under which they were made, not misleading or arising out of any untrue statement or alleged untrue statement of a material fact included in any preliminary prospectus or the Prospectus (or any amendment or supplement thereto), or the omission or alleged omission therefrom of a material fact required to be stated therein or necessary in order to make the statements therein, in the light of the circumstances under which they were made, not misleading;

provided, however, that this Section shall not apply to any loss, liability, claim, damage or expense to the extent arising out of any untrue statement or omission or alleged untrue statement or omission made in reliance upon and in conformity with written information furnished to the Company by or on behalf of the Holders, or any person, if any, who controls the Holders expressly for use in the Registration Statement (or any amendment thereto), or any preliminary prospectus or the Prospectus (or any amendment or supplement thereto).

(b) The Holders agree to indemnify and hold harmless the Company, and each person, if any, who controls the Company within the meaning of either Section 15 of the Securities Act or Section 20 of the Exchange Act severally and not jointly against any and all loss, liability, claim, damage and expense described in the indemnity contained in Section

- 4 -

1.5(a)(i), as incurred, but only with respect to untrue statements or omissions, or alleged untrue statements or omissions, made in the Registration Statement (or any amendment thereto) or any preliminary prospectus or the Prospectus (or any amendment or supplement thereto) in reliance upon and in conformity with written information furnished to the Company by or on behalf of the Holders expressly for use in the Registration Statement (or any amendment thereto) or the Prospectus (or any amendment or supplement thereto).

(c) Each party entitled to indemnification under this Section 1.5 (the “Indemnified Party”) shall give notice to the party required to provide indemnification (the “Indemnifying Party”) promptly after such Indemnified Party has actual knowledge of any claim as to which indemnity may be sought and shall permit the Indemnifying Party to assume the defense of any such claim or any litigation resulting therefrom, provided that counsel for the Indemnifying Party, who shall conduct the defense of such claim or any litigation resulting therefrom, shall be approved by the Indemnified Party (whose approval shall not be withheld unreasonably), and the Indemnified Party may participate in such defense at such Indemnified Party’s expense. The failure of any Indemnified Party to give notice as provided herein shall relieve the Indemnifying Party of its obligations under this Section 1.5 only if such failure is prejudicial to the ability of the Indemnifying Party to defend such action, and such failure shall in no event relieve the Indemnifying Party of any liability that he or it may have to any Indemnified Party otherwise than under this Section 1.5. No Indemnifying Party, in the defense of any such claim or litigation, shall, except with the consent of each Indemnified Party, consent to entry of any judgment or enter into any settlement that does not include as an unconditional term thereof the giving by the claimant or plaintiff to such Indemnified Party of a release from all liability with respect to such claim or litigation, provided that such unconditional release may be subject to a parallel release of a claimant or plaintiff by such Indemnified Party from all liability in respect of claims or counterclaims asserted by such Indemnified Party.

1.6 Information by Holders and Other Shareholders. Each Holder shall furnish to the Company such information regarding such Holder and the distribution proposed by such Holder as the Company may request in writing and as shall be required in connection with any Registration Statement.

1.7 Rule 144 Reporting. With a view to making available the benefits of certain rules and regulations of the SEC that may permit the sale of the Common Stock to the public without registration, the Company shall for so long as Registrable Securities are outstanding:

(a) make and keep public information available as those terms are understood and defined in Rule 144 promulgated by the SEC under the Securities Act (“Rule 144”);

(b) file with the SEC in a timely manner all reports and other documents required of the Company under the Securities Act and the Securities Exchange Act; and

(c) so long as any Holder owns any securities constituting or representing Registrable Securities, furnish to such Holder upon request a written statement by the Company as to its compliance with the reporting requirements of Rule 144, and of the Securities Act and the Securities Exchange Act.

- 5 -

1.8 Removal of Legends. If requested by a Holder, cooperate with such Holder to facilitate the timely preparation and delivery of certificates representing Registrable Securities to be delivered to a transferee pursuant to the Registration Statement, which certificates shall be free, to the extent permitted by applicable law and permissible under the terms of the Merger Agreement, of all restrictive legends, and to enable such Registrable Securities to be in such denominations and registered in such names as any such Holders may reasonably request.

1.9 Listing. The Company will cause all Registrable Securities to be listed or otherwise eligible for full trading privileges on the principal national securities exchange on which the Common Stock are then listed or quoted, not later than the date on which the Registrable Securities are issued by the Company to a Holder. The Company will use commercially reasonable efforts to continue the listing or trading privilege for all Registrable Securities on such exchange. The Company will as promptly as practicable notify the Holders of, and confirm in writing, the delisting of the Common Stock by such exchange.

2. MISCELLANEOUS.

2.1 Notices. All notices and other communications provided for or permitted hereunder shall be made in writing by hand delivery, by electronic facsimile transfer or by courier guaranteeing overnight delivery, and shall be deemed given (i) when made, if made by hand delivery, (ii) upon confirmation, if made by electronic facsimile transfer, (iii) one Business Day after being deposited with such courier, if made by overnight courier, to the parties as follows:

(a) if to a Holder, at the address for such Holder then appearing in the books of the Company;

With a copy to:

Goodwin Procter LLP

Attention: Stuart M. Cable, Esq.

Exchange Place

53 State Street

Boston, Massachusetts 02109

Facsimile: (617)  ###-###-####

(b) If to the Company, to:

Flowers Foods, Inc.

Attention: Stephen R. Avera, Esq.

1919 Flowers Circle

Thomasville, GA 31757

Facsimile: (229)  ###-###-####

- 6 -

With a copy to:

Jones Day

Attention: Sterling A. Spainhour, Jr., Esq.

1420 Peachtree Street, N.E.

Suite 800

Atlanta, Georgia 30309

Facsimile: (404)  ###-###-####

2.2 Governing Law. This Agreement shall be governed and construed under the laws of the State of Delaware, without regard to conflicts of laws and principles thereof.

2.3 Successors and Assigns. The rights and obligations set forth in this Agreement shall inure to the benefit of and be binding upon the parties hereto and their respective legal representatives, successors and assigns. Any Holder may, at its election, at any time or from time to time, assign its rights under this Agreement, in whole or in part, to a Permitted Transferee.

2.4 Captions. The captions of the several sections and paragraphs of this Agreement are included for reference only and shall not limit or otherwise affect the meaning thereof.

2.5 Amendments. Neither this Agreement nor any term of provision hereof may be amended, waived, discharged or terminated except in writing signed by all parties to this Agreement.

2.6 Counterparts. This Agreement may be executed in two or more counterparts, each of which shall be deemed an original but all of which taken together shall constitute but one and the same instrument.

2.7 Severability. If any term, provision, covenant or restriction of this Agreement is held to be invalid, illegal, void or unenforceable, the remainder of the terms, provisions, covenants and restrictions set forth herein shall remain in full force and effect and shall in no way be affected, impaired or invalidated thereby, and the parties hereto shall use their best efforts to find and employ an alternative means to achieve the same or substantially the same result as that contemplated by such term, provision, covenant or restriction, it being intended that all of the rights and privileges of the parties hereto shall be enforceable to the fullest extent permitted by law.

2.8 Entire Agreement. This Agreement is intended by the parties hereto as a final expression of their agreement and is intended to be a complete and exclusive statement of the agreement and understanding of the parties hereto in respect of the subject matter contained herein and the registration rights granted by the Company with respect to the Registrable Securities.

2.9 Termination. This Agreement and the obligations of the parties hereunder shall terminate upon the end of the Effectiveness Period, except for any liabilities or obligations under Sections 1.3, 1.5 or 1.6 hereof, each of which shall remain in effect in accordance with its terms.

- 7 -

[SIGNATURES APPEAR ON SUCCEEDING PAGES]

- 8 -

IN WITNESS WHEREOF, the parties have executed this Registration Rights Agreement on the date first written above.