Exhibit 99.9

Request for Extension of Scheduled Termination Date and

Agreement to Extend the VRDP Shares Fee Agreement

Dated as of April 15, 2013

BlackRock MuniHoldings New Jersey Quality Fund, Inc., as issuer (the “Fund”), and Bank of America, N.A., as liquidity provider (the “Liquidity Provider”) hereby acknowledge (i) that on March 27, 2013, in accordance with Section 2.02 of the VRDP Shares Fee Agreement, dated as of June 30, 2011, between the Fund and the Liquidity Provider (the “Original VRDP Shares Fee Agreement”), the Fund delivered to the Liquidity Provider a written request to extend the Scheduled Termination Date of the Original VRDP Shares Fee Agreement and the VRDP Shares Purchase Agreement to June 30, 2014 (the “Original Renewal Request”), and (ii) that on April 3, 2013, the Liquidity Provider requested that the Original Renewal Request be amended to extend the Scheduled Termination Date to June 25, 2014.

In accordance with Section 2.02 of the Original VRDP Shares Fee Agreement, the Fund hereby requests an extension of the Scheduled Termination Date of the Original VRDP Shares Fee Agreement and the VRDP Shares Purchase Agreement to June 25, 2014, effective upon acceptance of this request by the Liquidity Provider, as evidenced by (i) the Fund delivering to the Liquidity Provider a copy hereof signed by the Fund and (ii) the Liquidity Provider signing and returning to the Fund a copy hereof, whereupon this Request for Extension of Scheduled Termination Date and Agreement to Extend VRDP Shares Fee Agreement (this “Agreement”) shall be a binding agreement of the parties hereto, and the extension of both the Original VRDP Shares Fee Agreement (as it may be further amended) and VRDP Shares Purchase Agreement (as it may be further amended) shall become effective without further action by any party.

Upon effectiveness of the extension of the Scheduled Termination Date of the Original VRDP Shares Fee Agreement to June 25, 2014, the Scheduled Termination Date of the VRDP Shares Purchase Agreement shall automatically be extended to June 25, 2014. The Fund will send a copy of the fully executed Agreement to the Tender and Paying Agent for its acknowledgement, with instructions to send a notice of the extension to the Holders of the VRDP Shares (with a copy to Beneficial Owners to the extent provided in the Tender and Paying Agent Agreement).

4.	Capitalized terms used herein that are not otherwise defined shall have the meanings assigned to them in the Original VRDP Shares Fee Agreement.

5.	This Agreement shall be construed in accordance with and governed by the laws of the State of New York, without regard to conflict of laws principles that would require the application of the laws of another jurisdiction.

THE PARTIES HERETO HEREBY SUBMIT TO THE NON-EXCLUSIVE JURISDICTION OF THE FEDERAL AND NEW YORK STATE COURTS LOCATED IN THE CITY OF NEW YORK IN CONNECTION WITH ANY DISPUTE RELATED TO THIS AGREEMENT OR ANY MATTERS CONTEMPLATED HEREBY.

6.	The parties hereto hereby confirm that the Original VRDP Shares Fee Agreement and the VRDP Shares Purchase Agreement remain in full force and effect in accordance with the terms and subject to the conditions set forth therein, except as modified by Section 6 of this Agreement.

7.	Effective as of June 26, 2013, section 2.05(a) of the Original VRDP Shares Fee Agreement is hereby deleted and replaced in its entirety with the following:

The Fund shall pay to the Liquidity Provider from June 26, 2013 to and including the date on which the Purchase Obligation under the VRDP Shares Purchase Agreement for all VRDP Shares has terminated, a monthly fee for each VRDP Share outstanding on the first calendar day of the immediately preceding calendar month, in an amount, equal to (a) the product of (i) 0.65% of 101.85% times $100,000 multiplied by (ii) the actual number of days from and including such first calendar day of the immediately preceding calendar month to and including the last calendar day of such immediately preceding month or, if applicable, the date of any prior redemption or liquidation for such VRDP Share (as the case may be) (b) divided by 365.

If any provision of this Agreement shall be held or deemed to be or shall, in fact, be invalid, inoperative or unenforceable as applied in any particular case in any or all jurisdiction or jurisdictions, because it conflicts with any provision of any constitution, statute, rule of public policy, or for any other reason, such circumstances shall not have the effect of rendering the provision in question invalid, inoperative or unenforceable in any other case, circumstance or jurisdiction, or of rendering any other provision or provisions of this Agreement invalid, inoperative or unenforceable to any extent whatsoever.

9.	This Agreement may be signed in counterparts, each of which shall be an original, with the same effect as if the signatures thereto and hereto were upon the same instrument.

[Signature Page Follows]

IN WITNESS WHEREOF, the parties hereto have caused this Agreement to be duly executed by their respective authorized officers as of the day and year first above written.

		BLACKROCK MUNIHOLDINGS NEW JERSEY QUALITY FUND, INC., as Issuer

	By:	/s/ Robert W. Crothers
		Name: Robert W. Crothers
		Title: Vice President

		BANK OF AMERICA, N.A. as Liquidity Provider

	By:	/s/ James Nacos
		Name: James Nacos
		Title: Authorized Signatory

Acknowledged by:

THE BANK OF NEW YORK MELLON,

as Tender and Paying Agent

By: /s/ Christina Sotiriou

Name: Christina Sotiriou

Title: Vice President