UNITED STATES

SECURITIES AND EXCHANGE COMMISSION

Washington, D.C. 20549

FORM 8-K

CURRENT REPORT

Pursuant to Section 13 or 15(d) of the

Securities Exchange Act of 1934

Date of Report (Date of earliest event reported): April 27, 2011

NuStar GP Holdings, LLC

(Exact name of registrant as specified in its charter)

Registrant’s telephone number, including area code: (210) 918-2000

(Former name or former address, if changed since last report.)

Check the appropriate box below if the Form 8-K filing is intended to simultaneously satisfy the filing obligation of the registrant under any of the following provisions:

The 2011 Annual Meeting of Unitholders (the “Annual Meeting”) of NuStar GP Holdings, LLC, a Delaware limited liability company (the “Company”), was held on April 27, 2011. A total of 36,631,883 of the Company’s common units were present or represented by proxy at the meeting, representing approximately 86.20% of all the votes entitled to be cast at the Annual Meeting. The matters submitted for a vote and the related results are as follows:

Proposal No. 1 – Election of two Class II directors to serve until the 2014 annual meeting of unitholders or until their respective successors are elected and have been qualified. The results of the votes taken were as follows:

Proposal No. 2 – Ratification of the appointment of KPMG LLP as the Company’s independent registered public accounting firm for the fiscal year ending December 31, 2011. The results of the votes taken were as follows:

Proposal No. 3 – Approval, by non-binding vote, of NuStar GP Holdings, LLC’s executive compensation. The results of the votes taken were as follows:

Proposal No. 4 – Recommendation, by non-binding vote, of the frequency of NuStar GP Holdings, LLC’s future votes on executive compensation. The results of the votes taken were as follows:

Pursuant to the foregoing votes: (i) the two Class II nominees listed above were elected to serve on the Company’s Board of Directors until the 2014 annual meeting of unitholders or until their respective successors are elected and have been qualified; (ii) the appointment of KPMG LLP to serve as the Company’s independent registered public accounting firm for the fiscal year ending December 31, 2011 has been ratified; (iii) The Company’s executive compensation has been approved by non-binding vote; and (iv) the frequency of non-binding votes on executive compensation shall be every three years.

SIGNATURES

Pursuant to the requirements of the Securities Exchange Act of 1934, the registrant has duly caused this report to be signed on its behalf by the undersigned hereunto duly authorized.