CHANGE OF CONTROL AGREEMENT

Exhibit 10.4

CHANGE OF CONTROL AGREEMENT

CHANGE OF CONTROL AGREEMENT (this “Agreement”) dated as of October 31, 2006, by and between COAST FINANCIAL HOLDINGS, INC. (the “Company”), a Florida bank holding corporation, and PAUL J. NIDASIO (the “Executive”), an individual.

W I T N E S S E T H:

WHEREAS, the Executive is presently employed by the Company or by one or more of its subsidiaries as a key employee (the Company and all of its subsidiaries are hereinafter referred to collectively as “Coast Bank”);

WHEREAS, in light of the competitive environment in the local market areas served by Coast Bank, the Board of Directors of the Company (hereinafter, the “Board of Directors”) has undertaken a review of the commitments made to Coast Bank management personnel in the event of a Change of Control (as defined below), and based on such review, has concluded that such commitments, if any, may not be sufficiently competitive in the current market;

WHEREAS, the Board of Directors has determined that it is in the best interests of the Company and its shareholders to assure that they will have the continued dedication of the Executive, notwithstanding the possibility of competing offers for the Executive’s services or the possibility, threat, or occurrence of a Change of Control of the Company; and

WHEREAS, the Board of Directors believes that it is imperative to diminish the inevitable distraction of the Executive by virtue of the personal uncertainties and risks created by competitive inducements for the Executive’s services or by a pending or threatened Change of Control and to encourage the Executive’s full attention and dedication to Coast Bank currently and in the event of any threatened or pending Change of Control of the Company;

NOW, THEREFORE, in consideration of the Executive’s continued employment, and the mutual covenants and agreements set forth herein, the parties agree as follows:

1. Resignation or Termination without Cause during or after a Change of Control; Company’s Obligation for Severance Pay in Consideration of Executive’s Non-compete Commitments. The Company, either by itself, or through its Affiliated Companies, as defined below, or through its successors, agrees to pay the Executive eighteen (18) months of the Executive’s current Base Salary, as defined below, less all payroll taxes required to be withheld by law, if the Executive resigns employment with those Coast Bank entities by which the Executive is employed, or if the Executive’s employment with these Coast Bank entities is terminated without Cause, as defined below, and where such resignation or termination occurs (i) within one year of the Occurrence of a Change of Control, as defined below, or (ii) during that period of time when there is a Pending Change of Control, as defined below. This compensation (“Severance Pay”) is offered to the Executive in lieu of any other severance compensation provided by the Company, or by the Affiliated Companies, or by their successors and assigns, for which the Executive might be eligible, and shall be paid in equal installments as salary continuation over the eighteen (18) month period following the later of the Change of Control, or

the Executive’s resignation or termination (the “Severance Period”), at regular payroll intervals; as consideration for the Severance Pay commitment offered by this Agreement, the Executive agrees, in the event of such resignation or termination, to comply with the protective covenants set forth in Section 2 of this Agreement. Provided, however, that in the event of the Executive’s breach of any of the protective covenants in Section 2 of the Agreement, the Company, or its Affiliated Companies, or their successors, may reduce the consideration provided for execution of the protective covenants by terminating any Severance Pay otherwise due and owing after breach. Further provided, that in no event shall the Executive be obligated to seek other employment or take any other action by way of mitigation of the Severance Pay provided pursuant to this Agreement; in other words, the Severance Pay offered pursuant to this Agreement shall not be reduced because the Executive fails to obtain mitigating employment or fails to seek mitigating employment.

2. Protective Covenants. In the event of a resignation or termination subject to Section 1 of this Agreement, the Executive agrees, in consideration of the Severance Pay commitments, to faithfully and fully adhere to the following protective covenants:

(a) Covenant Not To Compete. The Executive agrees, during the Severance Period, not to engage, either directly or indirectly, in the business of banking, in the Company’s Market Area. “Engaging” includes, but is not limited to, being employed by, contracting with, working for, owning (in whole or in part), providing services to or for, lending assistance to or for, or consulting with or for the benefit of any legal or natural person; provided, however, that the Executive may own shares of stock in any banking corporation whose shares of stock are registered under Section 12 of the Exchange Act, as long as the Executive acquired the shares for investment purposes only and further provided that the Executive does not own, directly or indirectly, more than two percent (2%) of the issued and outstanding shares of any class of stock of such corporation. The “Company’s Market Area” is defined as comprising all Florida counties where Coast Bank had an office as of the day prior to the Occurrence of a Change of Control, and all Florida Counties in which Coast Bank, as of the day prior to the Occurrence of a Change of Control, had a definitive plan to locate new offices prior to or within the Severance Period.

(b) Covenants Relating to Customers and Prospective Customers. The Executive agrees, during the Severance Period, and only as to the Company’s Market Area, not to do any of the following: (i) solicit (directly or indirectly) any Company customers, or the customers of any Affiliated Companies, or their successors or assigns, to do business with a legal or natural person other than the Company, or the Affiliated Companies, or their successors or assigns; (ii) solicit (directly or indirectly) any prospective customers of the Company or the Affiliated Companies, or their successors or assigns, to do business with a legal or natural person other than the Company or the Affiliated Companies, or their successors or assigns; and (iii) solicit (directly or indirectly) any customers to cease doing business with the Company or the Affiliated Companies, or their successors or assigns.

(c) Covenants Relating to Employees. The Executive agrees, during the Severance Period, that the Executive will not solicit or attempt to persuade Company or Affiliated Company employees, or employees of the Company’s successors or assigns, to terminate their employment, and accept other employment within the Company’s Market Area.

2

This covenant specifically prohibits solicitation of employees, in the event of resignation or termination of the Executive’s employment, to work with or for the Executive in a banking business in the Company’s Market Area during the Severance Period.

(d) Related Provisions. The Executive agrees that the rights of the Company, the Affiliated Companies, and their successors and assigns provided in Section 2 of this Agreement are special, unique and of extraordinary character and that they would be without an adequate remedy at law if the Executive violated any of the covenants set forth above. Accordingly, the Executive agrees that the Company or any of the Affiliated Companies or any of their successors or assigns would be entitled to injunctive relief to enforce such covenants. It is also agreed that each of the covenants set forth in Section 2 of this Agreement is an agreement independent of any other provisions in this Agreement, and that if any such covenant is held invalid, void or unenforceable, such invalidity, voidness or unenforceability shall not render any other provision of this Agreement unenforceable. It is the parties’ intent that any covenant held overbroad by any court be enforced to the maximum extent deemed reasonable by that court. The parties also agree that in the event of breach of one of the covenants in this Section 2 by the Executive, any injunction may be extended by the length of time during which the Executive is acting in breach of the covenant. The existence of any claim of the Executive against the Company or the Affiliated Companies, or their successors or assigns, whether based on this Agreement or otherwise, shall not constitute a defense to the enforcement by the Company or the Affiliated Companies, or by their successors or assigns, of the Section 2 covenants.

3. Definitions.

(a) Change of Control. For purposes of this Agreement, a “Change of Control” shall be deemed to have occurred if:

(i) any individual, entity, or group (within the meaning of Sections 13(d)(3) or 14(d)(2) of the Exchange Act), is or becomes, directly or indirectly, the “beneficial owner” (as defined by Rule 13d-3 promulgated under the Securities Exchange Act of 1934 (“Exchange Act”)) of 25% or more of the combined voting power of the then outstanding securities of the Company, entitled to vote generally in the election of Company Directors (“Voting Securities”); provided, however, that any acquisition by the following will not constitute a Change of Control:

(A) the Company or any Affiliated Companies,

(B) any employee benefit plan (or related trust) of the Company or any Affiliated Companies, or

(C) any corporation, bank, or other financial institution with respect to which, following such acquisition, more than 50% of the combined voting power of the outstanding voting securities of such corporation entitled to vote generally in the election of directors is then beneficially owned by the persons who were the beneficial owners of the Voting Securities immediately prior to such acquisition in substantially the same proportion as their ownership immediately prior to such acquisition of the Voting Securities; or

3

(ii)(A) a tender offer or an exchange offer is made to acquire securities of the Company whereby following such offer the offerees will hold, control, or otherwise have the direct or indirect power to exercise voting control over 50% or more of the Voting Securities, or (B) Voting Securities are first purchased pursuant to any other tender or exchange offer; or

(iii) as a result of a tender offer or exchange offer for the purchase of securities of the Company (other than such an offer by the Company for its own securities), or as a result of a proxy contest, merger, consolidation, or sale of assets, or as a result of a combination of the foregoing, during any period of two consecutive years, individuals who, at the beginning of such period constitute the Company Board of Directors, plus any new Directors of the Company whose election or nomination for election by the Company’s stockholders was or is approved by a vote of at least two-thirds of the Directors of the Company then still in office who either were Directors of the Company at the beginning of such two year period or whose election or nomination for election was previously so approved (but excluding for this purpose, any individual whose initial assumption of office was or is in connection with the actual or threatened election contest relating to the election of Directors of the Company (as such term is used in Rule 14a-11 of Regulation 14A promulgated under the Exchange Act)), cease for any reason during such two year period to constitute at least two-thirds of the members of the Board; or

(iv) the stockholders of the Company approve a reorganization, merger, consolidation, or other combination, with or into any other corporation or entity regardless of which entity is the survivor, other than a reorganization, merger, consolidation, or other combination, which would result in the Voting Securities outstanding immediately prior thereto continuing to represent (either by remaining outstanding or being converted into Voting Securities of the surviving entity) at least 60% of the combined voting power of the Voting Securities or of the voting securities of the surviving entity outstanding immediately after such reorganization, merger, consolidation, or other combination; or

(v) the stockholders of the Company approve a plan of liquidation or winding-up of the Company or an agreement for the sale or disposition by the Company of all or substantially all of the Company’s assets, or any distribution to security holders of assets of the Company having a value equal to 30% or more of the total value of all assets of the Company.

(b) Occurrence of a Change of Control. A Change of Control will be deemed to have occurred on the following dates:

(i) with respect to any acquisition referred to in Section 2(a)(i) above, the date on which the acquisition of such percentage shall have been completed;

(ii) with respect to a tender or exchange offer, the date the offer referred to in Section 2(a)(ii)(A) above is made public or when documents are filed with the Securities and Exchange Commission in connection therewith pursuant to Section 14(d) of the Exchange Act, or the date of the purchase referenced in Section 2(a)(ii)(B);

4

(iii) with respect to a change in the composition of the Company Board of Directors referred to in Section 2(a)(iii), the date on which such change is adopted or is otherwise effective, whichever first occurs; or

(iv) with respect to any stockholder approval referred to in Section 2(a)(iv) or (v), the date of any approval.

(c) Pending Change of Control. A Pending Change of Control exists during a period of time commencing after the occurrence of a Transaction Event, as defined below, and ending after the Occurrence of a Change of Control. Accordingly, a Pending Change of Control only exists if there is both a Transaction Event, and, subsequently, a Change of Control, and there is no right to compensation under this Agreement unless the Executive resigns or is terminated without Cause during that period of time between the Transaction Event and the Occurrence of a Change of Control (Transaction Events which do not result, for any reason, in a Change of Control, create no right to compensation under this Agreement in the event of Executive’s resignation or termination). The “Transaction Events” which commence a Pending Change of Control are as follows: (i) the signing of a definitive agreement for a transaction which, if consummated, would result in a Change of Control; (ii) the commencement of a tender offer which, if consummated, would result in a Change of Control; or (iii) the circulation of a proxy statement seeking proxies in opposition to management in an election contest which, if successful, would result in a Change of Control.

(d) Base Salary. The Executive’s Base Salary shall be the Executive’s current base salary at the time of resignation or termination pursuant to Paragraph 1 hereof, regardless of whether that base salary is paid by the Company, or by any Affiliated Companies, or by their successors or assigns, and excluding any bonuses, other compensation, and the value of any benefits provided to the Executive in connection with Company employment.

(e) Affiliated Companies. The term “Affiliated Companies” shall include any company, bank, or financial institution controlled by, controlling or under common control with the Company or Coast Bank of Florida.

(f) Cause. For purposes of this Agreement, “Cause” shall mean, and be limited to: (i) the failure or refusal of the Executive to render services to the Company or any Affiliated Companies (other than failure due to Disability), or a material violation of a written policy of the Company or of the Affiliated Companies, but in either event, only after the Executive is provided written notice of this alleged failure or refusal or violation, and an opportunity of two weeks to cure the alleged failure or refusal or violation; (ii) an act or omission by the Executive which would be either a felony under applicable law, or a misdemeanor involving moral turpitude under applicable law, regardless of whether or not the Executive is prosecuted for this crime, and if prosecuted, regardless of the eventual disposition of the case; provided, however, that in the event there is not a criminal conviction or other adjudication of guilt, there must be sufficient evidence of a crime by the Executive, admissible in a court of law, to prove, by a preponderance of the evidence, that the Executive committed such acts; or (iii) a

5

serious act of misconduct in connection with work by the Executive, including, but not limited to, falsification of documents, dishonesty in connection with the business of the Company or any Affiliated Companies, misrepresentations to the Board of Directors of the Company, or a breach of the Executive’s duty of loyalty or other fiduciary duties owed to the Company or any Affiliated Companies.

4. Company’s Obligation as to Successors. The Company will require any successor (whether direct or indirect, by purchase, merger, consolidation, or otherwise) to all or substantially all of the business and/or the assets of the Company to expressly assume and agree to perform this Agreement in the same manner and to the same extent that the Company would be required to perform it if no such succession had taken place.

5. Assignment. This Agreement may not be assigned by the Executive. This Agreement may be assigned by the Company or its Affiliated Companies, and shall inure to the benefit of the Company’s and its Affiliated Companies’ successors and assigns (accordingly, the Company’s and the Affiliated Companies’ rights relating to the Executive’s compliance with the protective covenants may be transferred or assigned to another business purchasing the assets or stock of the Company or its Affiliated Companies).

6. Miscellaneous. This Agreement sets forth all agreements and understandings relating to any Change of Control payments to the Executive, superseding any previous oral or written agreements relating to this subject. This Agreement shall be governed by the laws of the State of Florida, and may not be changed, modified, released, discharged, abandoned, or otherwise amended, in whole or in part, except by a document in writing signed by the Executive and the Company.

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

6