Exhibit 99.8

BLACKROCK MUNIHOLDINGS NEW YORK QUALITY FUND, INC.

100 BELLEVUE PARKWAY

WILMINGTON, DELAWARE 19809

June 25, 2012

Bank of America, N.A.

One Bryant Park

1111 Avenue of the Americas, 9th Floor

New York, NY 10036

Re: VRDP Shares Fee Agreement

Dear James Nacos/Thomas Visone:

Reference is hereby made to the VRDP Shares Fee Agreement, dated as of June 30, 2011, by and between BlackRock MuniHoldings New York Quality Fund, Inc. (the “Fund”) and Bank of America, N.A. (“BOFA”) (the "Fee Agreement").  Section 6.05 of the Fee Agreement provides that the Fund will use its best efforts to maintain a long-term credit rating of the Fund’s variable rate demand preferred shares (the “VRDP Shares”) of "Aaa" by Moody's and a long-term issue credit rating of the Fund’s VRDP Shares of "AAA" by Fitch (or the highest equivalent ratings category for preferred stock furnished by at least two Rating Agencies).

The Fund understands that BOFA intends to waive the Fund’s obligation under Section 6.05 of the Fee Agreement to use best efforts to maintain a long-term credit rating of “Aaa” by Moody’s.  This letter confirms that the Fund will no longer be required to comply with Section 6.05 of the Fee Agreement, and that the Fund will instead use its best efforts to maintain a long-term credit rating of the Fund’s VRDP Shares of at least “Aa3” by Moody’s and a long-term issue credit rating of the Fund’s VRDP Shares of “AAA” by Fitch (or the highest equivalent ratings category for preferred stock furnished by at least two Rating Agencies).

The Fee Agreement shall remain in full force and effect in accordance with the terms and subject to the conditions set forth therein, except as modified by this letter.  Capitalized terms used herein that are not otherwise defined shall have the meanings assigned to them in the Fee Agreement.

This letter shall be construed in accordance with and governed by the domestic law of the State of New York, and BOFA and the Fund 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 letter or any matters contemplated hereby.

1

Please acknowledge and agree to the foregoing by signing the enclosed copy of this letter in the space provided below and returning the executed copy to the Fund.  This letter may be executed in any number of counterparts, each of which when executed, shall be deemed to be an original and all of which together shall be deemed to be one and the same instrument binding upon all of the parties hereto notwithstanding the fact that all parties are not signatory to the original or the same counterpart.  For purposes of this letter, facsimile signatures shall be deemed originals.

Sincerely,
BLACKROCK MUNIHOLDINGS NEW YORK QUALITY FUND, INC.
By:	/s/ Robert W. Crothers
	Name:  Robert W. Crothers
	Title:  Vice President

Accepted and agreed to as of the
first date written above:
BANK OF AMERICA, N.A.
By:	/s/ James Nacos
	Name:  James Nacos
	Title:  Authorized Signatory