AMENDED AND RESTATED CHANGE-IN-CONTROL AGREEMENT ROBERT A. EWING

EXHIBIT 10B.4

AMENDED AND RESTATED

CHANGE-IN-CONTROL AGREEMENT

ROBERT A. EWING

THIS AMENDED AND RESTATED CHANGE IN CONTROL AGREEMENT (this “Agreement”), is made as of this 11^th day of February, 2008, among VALLEY NATIONAL BANK (“Bank”), a national banking association with its principal office at 1455 Valley Road, Wayne, New Jersey, VALLEY NATIONAL BANCORP (“Valley”), a New Jersey corporation which maintains its principal office at 1455 Valley Road, Wayne, New Jersey (Valley and the Bank collectively are the “Company”) and ROBERT A. EWING the “Executive”).

BACKGROUND

WHEREAS, the Executive has been continuously employed by the Bank for at least three full years;

WHEREAS, the Boards of Directors of the Bank and Valley (either one, the “Board of Directors” and, together, the “Company Boards”) believe that the future services of the Executive are of great value to the Bank and Valley and that it is important for the growth and development of the Bank that the Executive continue in the Executive’s position;

WHEREAS, if the Company receives any proposal from a third person concerning a possible business combination with, or acquisition of equities securities of, the Company, the Company Boards believe it is imperative that the Company and the Company Boards be able to rely upon the Executive to continue in the Executive’s position, and that they be able to receive and rely upon the

1

Executive’s advice, if they request it, as to the best interests of the Company and its shareholders, without concern that the Executive might be distracted by the personal uncertainties and risks created by such a proposal;

WHEREAS, to achieve that goal, and to retain the Executive’s services prior to any such activity, the Company Boards and the Executive have agreed to enter into this Agreement to govern the Executive’s termination benefits in the event of a Change in Control of the Company, as hereinafter defined.

NOW, THEREFORE, to assure the Company that it will have the continued dedication of the Executive and the availability of the Executive’s advice and counsel notwithstanding the possibility, threat or occurrence of a bid to take over control of the Company, and to induce the Executive to remain in the employ of the Company, and for other good and valuable consideration, the Company and the Executive, each intending to be legally bound hereby agree as follows:

1. Definitions

a. Base Salary. “Base Salary”, as used in Section 9 hereof, means the annual cash base salary (excluding any bonus and the value of any fringe benefits) paid to the Executive at the time of the termination of employment unless such amount has been reduced after a Change in Control, in which case such amount shall be the highest base salary in effect during the 18 months prior to the Change in Control.

b. Cause. For purposes of this Agreement “Cause” with respect to the termination by the Company of Executive’s employment shall mean (i) willful and continued failure by

2

the Executive to perform the duties for the Company contemplated under this Agreement after at least one warning in writing from the Board of Directors identifying specifically any such failure; (ii) the willful engaging by the Executive in misconduct which causes material injury to the Company as specified in a written notice to the Executive from the Board of Directors; or (iii) conviction of a crime, other than a traffic violation, habitual drunkenness, drug abuse, or excessive absenteeism other than for illness, after a warning (with respect to drunkenness or absenteeism only) in writing from the Board of Directors to refrain from such behavior. No act or failure to act on the part of the Executive shall be considered willful unless done, or omitted to be done, by the Executive not in good faith and without reasonable belief that the action or omission was in the best interest of the Company.

c. Change in Control. “Change in Control” means any of the following events: (i) when Valley or a Valley Subsidiary acquires actual knowledge that any person (as such term is used in Sections 13(d) and 14(d)(2) of the Exchange Act), other than an affiliate of Valley or a Valley Subsidiary or an employee benefit plan established or maintained by Valley, a Valley Subsidiary or any of their respective affiliates, is or becomes the beneficial owner (as defined in Rule 13d-3 of the Exchange Act) directly or indirectly, of securities of Valley representing more than twenty-five percent (25%) of the combined voting power of Valley’s then outstanding securities (a “Control Person”); (ii) upon the first purchase of Valley’s common stock pursuant to a tender or exchange offer (other than a tender or exchange offer made by Valley, a Valley Subsidiary or an employee benefit plan established or maintained by Valley, a Valley Subsidiary or any of their respective affiliates); (iii) the consummation of (A) a transaction, other than a Non-Control Transaction, pursuant to which Valley is merged

3

with or into, or is consolidated with, or becomes the subsidiary of another corporation, (B) a sale or disposition of all or substantially all of Valley’s assets or (C) a plan of liquidation or dissolution of Valley; (iv) if during any period of two (2) consecutive years, individuals (the “Continuing Directors”) who at the beginning of such period constitute the Board of Directors of Valley (the “Valley Board”) cease for any reason to constitute at least 60% thereof or, following a Non-Control Transaction, 60% of the board of directors of the Surviving Corporation; provided that any individual whose election or nomination for election as a member of the Valley Board (or, following a Non-Control Transaction, the board of directors of the Surviving Corporation) was approved by a vote of at least two-thirds of the Continuing Directors then in office shall be considered a Continuing Director; or (v) upon a sale of (A) common stock of the Bank if after such sale any person (as such term is used in Section 13(d) and 14(d)(2) of the Exchange Act) other than Valley, an employee benefit plan established or maintained by Valley or a Valley Subsidiary, or an affiliate of Valley or a Valley Subsidiary, owns a majority of the Bank’s common stock or (B) all or substantially all of the Bank’s assets (other than in the ordinary course of business). For purposes of this paragraph: (I) Valley will be deemed to have become a subsidiary of another corporation if any other corporation (which term shall include, in addition to a corporation, a limited liability company, partnership, trust, or other organization) owns, directly or indirectly, 50 percent or more of the total combined outstanding voting power of all classes of stock of Valley or any successor to Valley; (II) “Non-Control Transaction” means a transaction in which Valley is merged with or into, or is consolidated with, or becomes the subsidiary of another corporation pursuant to a definitive agreement providing that at least 60% of the directors of the

4

Surviving Corporation immediately after the transaction are persons who were directors of Valley on the day before the first public announcement relating to the transaction; (III) the “Surviving Corporation” in a transaction in which Valley becomes the subsidiary of another corporation is the ultimate parent entity of Valley or Valley’s successor; (IV) the “Surviving Corporation” in any other transaction pursuant to which Valley is merged with or into another corporation is the surviving or resulting corporation in the merger or consolidation; and (V) “Valley Subsidiary” means any corporation in an unbroken chain of corporations, beginning with Valley, if each of the corporations other than the last corporation in the unbroken chain owns stock possessing 50% or more of the total combined voting power of all classes of stock in one of the other corporations in such chain.

d. Continuously Employed. “Continuously employed”, as used in Section 9, means continuously employed by the Bank but excludes any period of employment by a bank or financial institution acquired by or merged into the Bank and excludes any period of employment by the Bank if such period is separated from the current employment with the Bank by a break in service (other a break in service resulting solely from illness, disability or family leave).

e. Contract Period. “Contract Period” shall mean the period commencing the day immediately preceding a Change in Control and ending on the earlier of (i) the first anniversary of the Change in Control or (ii) the death of the Executive. For the purpose of this Agreement, a Change in Control shall be deemed to have occurred at the date specified in the definition of Change-in-Control.

5

f. Exchange Act. “Exchange Act” means the Securities Exchange Act of 1934, as amended.

g. Good Reason. When used with reference to a voluntary termination by Executive of employment with the Company, “Good Reason” shall mean any of the following, if taken without Executive’s express written consent:

(1) The assignment to Executive of any duties inconsistent with, or the reduction of powers or functions associated with, Executive’s position, duties, responsibilities and status with the Company immediately prior to a Change in Control. A change in title or positions resulting merely from a merger of the Bank or Valley into or with another bank or company which does not downgrade in any way the Executive’s powers, duties and responsibilities shall not meet the requirements of this paragraph;

(2) A reduction by the Company in Executive’s annual base compensation as in effect immediately prior to a Change in Control or the failure to award Executive annual increases in accordance herewith;

(3) A failure by the Company to continue any bonus plan in which Executive participated immediately prior to the Change in control or a failure by the Company to continue Executive as a participant in such plan on at least the same basis as Executive participated in such plan prior to the Change in Control;

(4) The Company’s transfer of Executive to another geographic location more than 35 miles from the Executive’s present office location, except for required travel on the Company’s business to an extent substantially consistent with Executive’s business travel obligations immediately prior to such Change in Control;

6

(5) The failure by the Company to continue in effect any employee benefit plan, program or arrangement (including, without limitation the Company’s retirement plan, life insurance plan, health and accident plan, disability plan, or long term stock incentive plan) in which Executive is participating immediately prior to a Change in Control (except that the Company may institute or continue plans, programs or arrangements providing Executive with substantially similar benefits); the taking of any action by the Company which would adversely affect Executive’s participation in or materially reduce Executive’s benefits under, any of such plans, programs or arrangements; the failure to continue, or the taking of any action which would deprive Executive, of any material fringe benefit enjoyed by Executive immediately prior to such Change in Control; or the failure by the Company to provide Executive with the number of paid vacation days to which Executive was entitled immediately prior to such Change in Control;

(6) The failure by the Company to obtain an assumption in writing of the obligations of the Company to perform this Agreement by any successor to the Company and to provide such assumption to the Executive prior to any Change in Control; or

(7) Any purported termination of Executive’s employment by the Company during the term of this Agreement which is not effected pursuant to all of the requirements of this Agreement; and, for purposes of this Agreement, no such purported termination shall be effective.

h. Pro-rata Bonus Amount. “Pro-rata Bonus Amount”, as used in Section 9,

7

means an amount equal to a “portion” of the highest cash bonus paid to the Executive in the three calendar years immediately prior to the Change in Control. The “portion” of such cash bonus shall be a fraction, the numerator of which is the number of calendar months or part thereof which the Executive has worked in the calendar year in which the termination occurs and the denominator of which is 12.

2. Employment. The Company hereby agrees to employ the Executive, and the Executive hereby accepts employment, during the Contract Period upon the terms and conditions set forth herein.

3. Position. During the Contract Period the Executive shall be employed as a Senior Officer by the bank, or such other corporate or divisional profit center as shall then be the principal successor to the business, assets and properties of the Company, with substantially the same title and the same duties and responsibilities as before the Change in Control. The Executive shall devote full time and attention to the business of the Company, and shall not during the Contract Period be engaged in any other business activity. This paragraph shall not be construed as preventing the Executive from managing any investments which do not require any service on the Executive’s part in the operation of such investments.

4. Cash Compensation. The Company shall pay to the Executive compensation for services during the Contract Period as follows:

a. Base Salary. A base annual salary equal to the annual salary in effect as of the Change in Control. The annual salary shall be payable in installments in accordance with the Company’s usual payroll method.

8

b. Annual Bonus. An annual cash bonus equal to at least the average of the bonuses paid to the Executive in the three years prior to the Change in Control. The bonus shall be payable at the time and in the manner which the Company paid such bonuses prior to the Change in Control.

c. Annual Review. The Board of Directors during the Contract Period shall review annually, or at more frequent intervals which the Board of Directors determines is appropriate, the Executive’s compensation and shall award the Executive additional compensation to reflect the Executive’s performance, the performance of the Company and competitive compensation levels, all as determined in the discretion of the Board of Directors.

5. Expenses and Fringe Benefits.

a. Expenses. During the Contract Period, the Executive shall be entitled to reimbursement for all business expenses incurred by the Executive with respect to the business of the Company in the same manner and to the same extent as such expenses were previously reimbursed to the Executive immediately prior to the Change in Control.

b. Other Benefits. The Executive also shall be entitled to vacations and sick days, in accordance with the practices and procedures of the Company, as such existed immediately prior to the Change in Control. During the Contract Period, the Executive also shall be entitled to hospital, health, medical and life insurance, and any other benefits enjoyed, from time to time, by senior officers of the Company, all upon terms as favorable as those enjoyed by other senior officers of the Company. Notwithstanding anything in this paragraph 5(b) to the contrary, if the Company adopts any

9

change in the benefits provided for senior officers of the Company, and such policy is uniformly applied to all officers of the Company (and any successor or acquiror of the Company, if any), then no such change shall be deemed to be contrary to this paragraph.

6. Termination for Cause. The Company shall have the right to terminate the Executive for Cause, upon written notice to the Executive of the termination which notice shall specify the reasons for the termination. In the event of termination for Cause the Executive shall not be entitled to any further benefits under this Agreement.

7. Disability. During the Contract Period if the Executive becomes permanently disabled, or is unable to perform the Executive’s duties hereunder for 4 consecutive months in any 12 month period, the Company may terminate the employment of the Executive. In such event, the Executive shall not be entitled to any further benefits under this Agreement.

8. Death Benefits. Upon the Executive’s death during the Contract Period, the Executive’s estate shall not be entitled to any further benefits under this Agreement.

9. Termination Without Cause or Resignation for Good Reason. The Company may terminate the Executive without Cause during the Contract Period by written notice to the Executive providing four weeks notice. The Executive may resign for Good Reason during the Contract Period upon four weeks’ written notice to the Company specifying facts and circumstances claimed to support the Good Reason. The Executive shall be entitled to give a Notice of Termination that his or her employment is being terminated for Good Reason at any time during the Contract Period, not later than twelve months after any occurrence of an event stated to constitute Good Reason. If the Company terminates the Executive’s employment during the Contract Period without Cause or if the Executive Resigns for Good Reason, the Company shall, subject to section 12 hereof:

a. Within 20 business days of the termination of employment pay the Executive a lump sum equal to: (i), if the Executive has been continuously employed by the Bank for less than 6 full years but more than 3 years, then six (6) months of Base Salary plus a Pro-rata Bonus Amount; or (ii), if the Executive has been continuously employed by the Bank for 6 full years or more, one (1) year of Base Salary plus a Pro-rata Bonus Amount.

10

b. the Company shall, within 20 business days of the termination of employment with the Company, pay the Executive a lump sum amount equal to one hundred percent (100%) of the premium of the life insurance coverage provided to a similarly situated active employee (based upon the coverage and rates in effect on the date the Executive terminates employment) for the equivalent period of the lump sum severance payment (i.e. one (1) year or two (2) years); and

c. the Company shall, within 20 business days of the termination of employment, pay the Executive a lump sum amount equal to one hundred twenty-five percent (125%) of (A) the aggregate COBRA premium amounts (based upon COBRA rates then in effect) for the equivalent period of the lump sum payment (i.e. six (6) months or one (1) year) of the medical and dental coverage that was being provided to the Executive (and his spouse) at the time of termination of employment with the Company, minus (B) the aggregate amount of any employee contribution that would have been required of the Executive (determined as of the termination of employment) for such period.

11

The Executive shall not have a duty to mitigate the damages suffered by the Executive in connection with the termination by the Company of the Executive’s employment without Cause or a resignation for Good Reason during the Contract Period. If the Company fails to pay the Executive any lump sum amounts due the Executive hereunder, the Executive, after giving 10 days’ written notice to the Company identifying the Company’s failure, shall be entitled to recover from the Company all of the Executive’s reasonable legal fees and expenses incurred in connection with the enforcement against the Company of the terms of this Agreement. The Executive shall be denied payment of his or her legal fees and expenses only if a court finds that the Executive sought payment of such fees without reasonable cause.

10. Resignation Without Good Reason. The Executive shall be entitled to resign from the employment of the Company at any time during the Contact Period without Good Reason, but upon such resignation the Executive shall not be entitled to any additional compensation for the time after which the Executive ceases to be employed by the Company, and shall not be entitled to any of the other benefits provided hereunder. No such resignation shall be effective unless in writing with four weeks’ notice thereof.

11. Non-Disclosure of Confidential Information.

a. Non-Disclosure of Confidential Information. Except in the course of the Executive’s employment with the Company and in the pursuit of the business of the Company or any of its subsidiaries or affiliates, the Executive shall not, at any time during or following the Contract Period, disclose or use, any confidential information or proprietary data of the Company or any of its subsidiaries or affiliates. The Executive agrees that, among other things, all information concerning the identity of and the Company’s relations with its customers is confidential information.

12

b. Specific Performance. Executive agrees that the Company does not have an adequate remedy at law for the breach of this section and agrees that the Executive shall be subject to injunctive relief and equitable remedies as a result of the breach of this section. The invalidity or unenforceability of any provision of this Agreement shall not affect the force and effect of the remaining valid portions.

c. Survival. This section shall survive the termination of the Executive’s employment hereunder and the expiration of this Agreement.

12. Certain Reduction of Payments by the Company.

a. Anything in this Agreement to the contrary notwithstanding, prior to the payment of any lump sum amount payable hereunder, the certified public accountants of the Company immediately prior to a Change of Control (the “Certified Public Accountants) shall determine as promptly as practical and in any event within 20 business days following the termination of employment of Executive whether any payment or distribution by the Company to or for the benefit of the Executive (whether paid or payable or distributed or distributable pursuant to the terms of this Agreement or otherwise) (a “Payment”) would more likely than not be nondeductible by the Company for Federal income purposes because of Section 280G of the Internal Revenue Code of 1986, as amended (the “Code”), and if it is then the aggregate present value of amounts payable or distributable to or for the benefit of Executive pursuant to this Agreement (such payments or distributions pursuant

13

to this Agreement are thereinafter referred to as “Agreement Payments”) shall be reduced (but not below zero) to the reduced Amount. For purposes of this paragraph, the “Reduced Amount” shall be an amount expressed in present value which maximizes the aggregate present value of Agreement Payments without causing any Payment to be nondeductible by the Company because of said Section 280G of the Code.

b. If under paragraph (a) of this section the Certified Public Accountants determine that any Payment would more likely than not be nondeductible by the Company because of Section 280G of the Code, the Company shall promptly give the Executive notice to that effect and a copy of the detailed calculation thereof and of the Reduced Amount, and the Executive may then elect, in the Executive’s sole discretion, which and how much of the Agreement Payments shall be eliminated or reduced (as long as after such election the aggregate present value of the Agreement Payments equals the Reduced Amount), and shall advise the Company in writing of his or her election within 20 business days of the receipt of notice. If no such election is made by the Executive within such 20-day period, the Company may elect which and how much of the Agreement Payments shall be eliminated or reduced (as long as after such election the Aggregate present Value of the Agreement Payments equals the Reduced Amount) and shall notify the Executive promptly of such election. For purposes of this paragraph, present Value shall be determined in accordance with Section 280G(d)(4) of the Code. All determinations made by the Certified Public Accountants shall be binding upon the Company and Executive shall be made within 20 business days of a termination of employment of Executive. With the consent of the Executive, the Company may suspend part or all of the lump sum payment due

14

under Section 9 hereof and any other payments due to the Executive hereunder until the Certified Public Accountants finish the determination and the Executive (or the Company, as the case may be) elect how to reduce the Agreement Payments, if necessary. As promptly as practicable following such determination and the elections hereunder, the Company shall pay to or distribute to or for the benefit of Executive such amounts as are then due to Executive under this Agreement and shall promptly pay to or distribute for the benefit of Executive in the future such amounts as become due to Executive under this Agreement.

c. As a result of the uncertainty in the application of Section 280G of the Code, it is possible that Agreement Payments may have been made by the Company which should not have been made (“Overpayment”) or that additional Agreement Payments which will have not been made by the Company could have been made (“Underpayment”), in each case, consistent with the calculation of the Reduced Amount hereunder. In the event that the Certified Public Accountants, based upon the assertion of a deficiency by the Internal Revenue Service against the Company or Executive which said Certified Public Accountants believe has a high probability of success, determines that an Overpayment has been made, any such Overpayment shall be treated for all purposes as a loan to Executive which Executive shall repay to the Company together with interest at the applicable Federal rate provided for in Section 7872(f)(2)(A) of the Code; provided, however, that no amount shall be payable by Executive to the Company in and for the extent such payment would not reduce the amount which is subject to taxation under Section 4999 of the Code. In the event that the Certified Public Accountants, based upon controlling precedent, determine that an Underpayment has occurred, any such Underpayment shall be promptly paid by the Company to or for the benefit of the Executive together with interest at the applicable Federal rate provided for in Section 7872(f)(2)(A) of the Code.

15

13. Term and Effect Prior to Change in Control.

a. Term. Except as otherwise provided for hereunder, this Agreement shall commence on the date hereof and shall remain in effect for a period of 3 years from the date hereof (the “Initial Term”) or until the end of the Contract Period, whichever is later. The Initial Term shall be automatically extended for an additional one year period on the anniversary date hereof (so that the Initial Term is always 3 years) unless, prior to a Change in Control, the Personnel and Compensation Committee of the Bank notifies the Executive in writing at any time that the Contract is not so extended, in which case the Initial Term shall end upon the later of (i) 3 years after the date hereof, or (ii) nine months after the date of such written notice.

b. No Effect Prior to Change in Control. This Agreement shall not effect any rights of the Company to terminate the Executive prior to a Change in Control or any rights of the Executive granted in any other agreement or contract or plan with the Company. The rights, duties and benefits provided hereunder shall only become effective upon and after a Change in Control. If the full-time employment of the Executive by the Company is ended for any reason prior to a Change in Control, this Agreement shall thereafter be of no further force and effect.

14. Severance Compensation and Benefits Not in Derogation of Other Benefits. Anything to the contrary herein contained notwithstanding, the payment or obligation to pay any monies, or granting of any benefits, rights or privileges to Executive as provided in this Agreement

16

shall not be in lieu or derogation of the rights and privileges that the Executive now has or will have under any plans or programs of or agreements with the Company, except that if the Executive received any payment hereunder, the Executive shall not be entitled to any payment under the Company’s severance policy for officers and directors.

15. Delay in Payment. Notwithstanding anything else to the contrary in this Agreement, the BEP, or any other plan, contract, program or otherwise, the Company (and its affiliates) are expressly authorized to delay any scheduled payments under this Agreement, the BEP, and any other plan, contract, program or otherwise, as such payments relate to the Executive, if the Company (or its affiliate) determines that such delay is necessary in order to comply with the requirements of Section 409A of the Internal Revenue Code. No such payment may be delayed beyond the date that is six (6) months following the Executive’s separation from service (as defined in Section 409A). At the end of such period of delay, the Executive will be paid the delayed payment amounts, plus interest for the period of any such delay. For purposes of the preceding sentence, interest shall be calculated using the six (6) month Treasury Bill rate in effect on the date on which the payment is delayed, and shall be compounded daily. If the conditions of the severance exception under Treasury Regulation Section 1.409A-1(b)(9)(iii) (or any successor Regulation thereto) are satisfied, payment of benefits shall not be delayed for six (6) months following termination of employment to the extent permitted under the severance exception.

16. Miscellaneous. This Agreement is the joint and several obligation of the Bank and Valley. The terms of this Agreement shall be governed by, and interpreted and construed in

17

accordance with the provisions of, the laws of New Jersey. This Agreement supersedes all prior agreements and understandings with respect to the matters covered hereby, including expressly any prior agreement with the Company concerning change in control benefits. The amendment or termination of this Agreement may be made only in a writing executed by the Company and the Executive, and no amendment or termination of this Agreement shall be effective unless and until made in such a writing. This Agreement shall be binding upon any successor (whether direct or indirect, by purchase, merge, consolidation, liquidation or otherwise) to all or substantially all of the assets of the Company. This Agreement is personal to the Executive and the Executive may not assign any of the Executive’s rights or duties hereunder but this Agreement shall be enforceable by the Executive’s legal representatives, executors or administrators. This Agreement may be executed in two or more counterparts, each of which shall be deemed an original, and it shall not be necessary in making proof of this Agreement to produce or account for more than one such counterpart.

18

IN WITNESS WHEREOF, Valley National Bank and Valley National Bancorp each have caused this Agreement to be signed by their duly authorized representatives pursuant to the authority of their Boards of Directors, and the Executive has personally executed this Agreement, all as of the day and year first written above.

19