Exhibit 99.1

NuStar GP Holdings, LLC Reports Highest Quarterly Earnings in

Company’s History; Previously Announced Increase in Quarterly

Distribution to $0.43 Per Unit

SAN ANTONIO, October 23, 2008 – NuStar GP Holdings, LLC (NYSE:NSH) today announced record earnings of $34.8 million, or $0.82 per unit, for the third quarter of 2008, nearly 2.5 times higher than the $14.1 million, or $0.33 per unit, earned in the third quarter of 2007. The third quarter 2008 results represent the highest quarterly earnings in the company’s history. Distributable cash flow available to unitholders for the third quarter of 2008 was $18.3 million, or $0.43 per unit, compared to $15.1 million, or $0.35 per unit, for the third quarter of 2007.

With respect to the quarterly distribution to unitholders for the third quarter of 2008, NuStar GP Holdings, LLC previously announced that its board of directors had increased the quarterly distribution rate to $0.43 per unit, which would equate to $1.72 per unit on an annual basis. This quarterly distribution represents an increase of $0.07 per unit, or 19.4 percent, over the $0.36 distribution for the second quarter of 2008 and third quarter of 2007 and will be paid on November 14, 2008, to holders of record as of November 5, 2008.

“NuStar GP Holdings, LLC’s record third quarter is due to NuStar Energy L.P.’s solid distribution increase and outstanding third quarter results, which primarily benefited from the strong contribution of the asphalt operations acquired in March. This allowed us to provide a significant increase in the distribution to our unitholders who benefit from the incentive distribution rights. NuStar Energy L.P.’s continued growth and disciplined financial strategy should translate into further distribution growth for NuStar GP Holdings, LLC,” 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 23, 2008, to discuss the financial results for the third quarter of 2008. Investors interested in listening to the presentation may call 800/622-7620, passcode 67543575. International callers may access the presentation by dialing 706/645-0327, passcode 67543575. The company intends to have a playback available following the presentation, which may be accessed by calling 800/642-1687, passcode 67543575. A live broadcast of the conference call will also be available on the company’s Web site at www.nustargp.com.

-More-

NuStar GP Holdings, LLC is a publicly traded limited liability company that owns the two percent general partner interest, an 18.5 percent limited partner interest and the incentive distribution rights in NuStar Energy L.P., one of the largest asphalt refiners and marketers in the 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 2007 annual report on Form 10-K and subsequent filings with the Securities and Exchange Commission.

-30-

NuStar GP Holdings, LLC

Consolidated Financial Information

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

	Three Months Ended September 30,						Nine Months Ended September 30,
	2008			2007			2008			2007
Statement of Income Data:
Equity in earnings of NuStar Energy L.P.	$	35,662		$	15,033		$	58,120		$	36,541
General and administrative expenses		(793	)		(665	)		(2,359	)		(2,208	)
Other expense, net		(36	)		—			(118	)		(2	)
Interest (expense) income, net		(57	)		29			(153	)		43
Income before income tax benefit (expense)		34,776			14,397			55,490			34,374
Income tax benefit (expense)		34			(313	)		103			(271	)
Net income	$	34,810		$	14,084		$	55,593		$	34,103
Basic and diluted net income per unit	$	0.82		$	0.33		$	1.31		$	0.80
Equity in Earnings of NuStar Energy L.P.:
General partner interest (2%)	$	2,888		$	927		$	4,069		$	2,176
General partner incentive distribution		6,929			4,915			17,835			13,238
General partner’s interest in earnings of NuStar Energy L.P.		9,817			5,842			21,904			15,414
Limited partner interest in earnings of NuStar Energy L.P.		26,566			9,912			38,379			23,290
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.	$	35,662		$	15,033		$	58,120		$	36,541
Distributable Cash (Note 1):
Cash distributions from NuStar Energy L.P. associated with:
General partner interest (2%)	$	1,318		$	1,041		$	3,740		$	2,992
Incentive distribution rights (Note 2):		6,929			4,915			18,365			13,238
Limited partner interest-common units		10,872			10,083			31,003			29,156
Total cash distributions from NuStar Energy L.P.		19,119			16,039			53,108			45,386
Deduct expenses of NuStar GP Holdings, LLC:
General and administrative expenses		(793	)		(665	)		(2,359	)		(2,208	)
Income tax benefit (expense)		34			(313	)		103			(271	)
Interest (expense) income, net		(57	)		29			(153	)		43
Distributable cash flow	$	18,303		$	15,090		$	50,699		$	42,950
Units outstanding		42,501,433			42,500,420			42,501,139			42,500,141
Distributable cash flow per unit	$	0.43		$	0.35		$	1.19		$	1.01
Cash distributions to be paid to the unitholders of NuStar GP Holdings, LLC:
Distribution per unit	$	0.43		$	0.36		$	1.15		$	1.02
Total distribution	$	18,276		$	15,300		$	48,876		$	43,350

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 to net cash provided by operating activities:

	Three Months Ended September 30,						Nine Months Ended September 30,
	2008			2007			2008			2007
Net Income	$	34,810		$	14,084		$	55,593		$	34,103
Less equity in earnings of NuStar Energy L.P.		(35,662	)		(15,033	)		(58,120	)		(36,541	)
Plus cash distributions from NuStar Energy L.P.		19,119			16,039			53,108			45,386
Plus other expense, net		36			—			118			2
Distributable cash flow		18,303			15,090			50,699			42,950
Less cash distributions from NuStar Energy L.P.		(19,119	)		(16,039	)		(53,108	)		(45,386	)
Plus distributions of equity in earnings of NuStar Energy L.P.		27,886			15,033			50,344			36,541
Net effect of changes in operating accounts		424			(1,276	)		(86	)		1,284
Net cash provided by operating activities	$	27,494		$	12,808		$	47,849		$	35,389

2. NuStar Energy L.P.'s net income allocation for the first quarter 2008 to general and limited partners reflected total cash distributions based upon the partnership interests outstanding as of March 31, 2008. NuStar Energy L.P. 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, the general partner's portion of the actual cash payment made with respect to the first quarter 2008, including the incentive distribution rights, was greater than the net income allocated to the general partner.