Exhibit 99.1

NuStar GP Holdings, LLC Reports Third Quarter 2009 Earnings and

Announces Quarterly Distribution Increase

SAN ANTONIO, October 27, 2009 – NuStar GP Holdings, LLC (NYSE: NSH) announced today distributable cash flow available to unitholders for the third quarter of 2009 of $18.9 million, or $0.44 per unit, compared to $18.3 million, or $0.43 per unit, for the third quarter of 2008. Third quarter 2009 earnings were $17.7 million, or $0.42 per unit, compared to $34.8 million, or $0.82 per unit, for the third quarter of 2008.

With respect to the quarterly distribution to unitholders for the third quarter of 2009, NuStar GP Holdings, LLC also announced that its board of directors has declared a distribution of $0.435 per unit, which would equate to $1.74 per unit on an annual basis. The distribution per unit for the first three quarters of 2009 is nearly 13 percent higher than the distribution for the same period in 2008. It also represents an increase over the $0.43 distribution for the second quarter of 2009 and third quarter of 2008. The third quarter 2009 distribution will be paid on November 17, 2009, to holders of record as of November 5, 2009.

“I am pleased to report an increase in the distribution to our unitholders supported by the recently announced distribution increase at NuStar Energy L.P. Our unitholders continue to benefit from the incentive distribution rights associated with the two percent general partner interest that provide cash flow growth leverage as NuStar Energy L.P. increases their distribution. We are excited about new growth opportunities at NuStar Energy L.P. and the potential it provides for continued growth in cash flows to NuStar GP Holdings, LLC unitholders,” said Curt Anastasio, Chief Executive Officer and President of NuStar Energy L.P. and NuStar GP Holdings, LLC.

A conference call with management is scheduled for 11:00 a.m. ET (10:00 a.m. CT) today, October 27, 2009, to discuss the financial results for the third quarter of 2009. Investors interested in listening to the presentation may call 800/622-7620, passcode 33734891. International callers may access the presentation by dialing 706/645-0327, passcode 33734891. The company intends to have a playback available following the presentation, which may be accessed by calling 800/642-1687, passcode 33734891. A live broadcast of the conference call will also be available on the company’s Web site at www.nustargp.com.

NuStar GP Holdings, LLC is a publicly traded limited liability company that owns the two percent general partner interest, an 18.4 percent limited partner interest and the incentive distribution rights in NuStar Energy L.P., one of the largest asphalt refiners and marketers in the

-More-

U.S. and the second largest independent liquids terminal operator in the nation with operations in the United States, the Netherlands Antilles, Canada, Mexico, the Netherlands and the United Kingdom. For more information, visit NuStar GP Holdings, LLC’s Web site at www.nustargp.com.

Cautionary Statement Regarding Forward-Looking Statements

This press release includes forward-looking statements regarding future events. All forward-looking statements are based on the company’s beliefs as well as assumptions made by and information currently available to the company. These statements reflect the company’s current views with respect to future events and are subject to various risks, uncertainties and assumptions. These risks, uncertainties and assumptions are discussed in NuStar GP Holdings, LLC’s 2008 annual report on Form 10-K and subsequent filings with the Securities and Exchange Commission. All information in this release is as of the date hereof, and we undertake no duty to update any forward-looking statement to conform the statement to actual results or changes in the company’s operations.

-30-

NuStar GP Holdings, LLC

Consolidated Financial Information

(Unaudited, Thousands of Dollars, Except Unit and Per Unit Data)

	Three Months Ended September 30,						Nine Months Ended September 30,
	2009			2008			2009			2008
Statement of Income Data:
Equity in earnings of NuStar Energy L.P.	$	18,051		$	35,662		$	52,780		$	58,120
General and administrative expenses		(679	)		(793	)		(2,156	)		(2,359	)
Other income (expense), net		22			(36	)		19			(118	)
Interest expense, net		(88	)		(57	)		(137	)		(153	)
Income before income tax benefit		17,306			34,776			50,506			55,490
Income tax benefit		420			34			603			103
Net income	$	17,726		$	34,810		$	51,109		$	55,593
Basic and diluted net income per unit	$	0.42		$	0.82		$	1.20		$	1.31
Equity in Earnings of NuStar Energy L.P.:
General partner interest	$	1,148		$	2,888		$	3,333		$	4,069
General partner incentive distribution		7,055			6,929			20,913			17,835
General partner’s interest in earnings of NuStar Energy L.P.		8,203			9,817			24,246			21,904
Limited partner interest in earnings of NuStar Energy L.P.		10,569			26,566			30,697			38,379
Amortization of step-up in basis related to NuStar Energy L.P.’s assets and liabilities		(721	)		(721	)		(2,163	)		(2,163	)
Equity in earnings of NuStar Energy L.P.	$	18,051		$	35,662		$	52,780		$	58,120
Distributable Cash Flow (Note 1):
Cash distributions from NuStar Energy L.P. associated with:
General partner interest	$	1,327		$	1,318		$	3,963		$	3,740
Incentive distribution rights (Note 2):		7,055			6,929			20,913			18,365
Limited partner interest-common units		10,895			10,872			32,552			31,003
Total cash distributions from NuStar Energy L.P.		19,277			19,119			57,428			53,108
Deduct expenses of NuStar GP Holdings, LLC:
General and administrative expenses		(679	)		(793	)		(2,156	)		(2,359	)
Income tax benefit		420			34			603			103
Interest expense, net		(88	)		(57	)		(137	)		(153	)
Distributable cash flow	$	18,930		$	18,303		$	55,738		$	50,699
Weighted average number of common units outstanding		42,504,238			42,501,433			42,503,937			42,501,139
Distributable cash flow per unit	$	0.44		$	0.43		$	1.31		$	1.19
Cash distributions to be paid to the unitholders of NuStar GP Holdings, LLC:
Distribution per unit	$	0.435		$	0.43		$	1.295		$	1.15
Total distribution	$	18,489		$	18,276		$	55,043		$	48,876

NuStar GP Holdings, LLC

Consolidated Financial Information

(Unaudited, Thousands of Dollars)

Notes:

1. NuStar GP Holdings, LLC utilizes distributable cash flow as a financial measure, which is not defined in United States generally accepted accounting principles. Management uses this financial measure because it is a widely accepted financial indicator used by investors to compare general partner performance. In addition, management believes that this measure provides investors an enhanced perspective of the ability to make a minimum quarterly distribution. Distributable cash flow is not intended to represent cash flows for the period, nor is it presented as an alternative to net income. It should not be considered in isolation or as a substitute for a measure of performance prepared in accordance with United States generally accepted accounting principles.

The following is a reconciliation of net income to distributable cash flow and net cash provided by operating activities:

	Three Months Ended September 30,						Nine Months Ended September 30,
	2009			2008			2009			2008
Net Income	$	17,726		$	34,810		$	51,109		$	55,593
Less equity in earnings of NuStar Energy L.P.		(18,051	)		(35,662	)		(52,780	)		(58,120	)
Plus cash distributions from NuStar Energy L.P.		19,277			19,119			57,428			53,108
Other (income) expense, net		(22	)		36			(19	)		118
Distributable cash flow		18,930			18,303			55,738			50,699
Less cash distributions from NuStar Energy L.P.		(19,277	)		(19,119	)		(57,428	)		(53,108	)
Plus distributions of equity in earnings of NuStar Energy L.P.		18,051			27,886			52,780			50,344
Net effect of changes in operating accounts		(3,834	)		424			4,606			(86	)
Net cash provided by operating activities	$	13,870		$	27,494		$	55,696		$	47,849

2. For the first quarter of 2008, NuStar Energy’s net income allocation to general and limited partners reflected total cash distributions based on the partnership interests outstanding as of March 31, 2008. NuStar Energy issued approximately 5.1 million common units in April 2008. Actual distribution payments are made within 45 days after the end of each quarter as of a record date that is set after the end of each quarter. As such, our portion of the actual distributions made with respect to the nine months ended September 30, 2008, including the incentive distribution rights, exceeded the net income allocation to us.