Exhibit 99.1

NuStar GP Holdings, LLC Reports Record First Quarter 2008 Earnings and Announces Quarterly Distribution

SAN ANTONIO, April 22, 2008 – NuStar GP Holdings, LLC (NYSE:NSH) today announced earnings of $15.5 million, or $0.36 per unit, for the first quarter of 2008, significantly higher than the $8.8 million, or $0.21 per unit, generated in the first quarter of 2007. Distributable cash flow available to unitholders for the first quarter of 2008 was $16.2 million, or $0.38 per unit, compared to $13.5 million, or $0.32 per unit, for the first quarter of 2007. The first quarter 2008 results represent the highest quarterly earnings and distributable cash flow in the company’s history.

With respect to the quarterly distribution to unitholders for the first quarter of 2008, NuStar GP Holdings, LLC also announced that its board of directors has declared a distribution of $0.36 per unit, or $1.44 per unit on an annual basis, which will be paid on May 16, 2008, to holders of record as of May 7, 2008. This quarterly distribution represents an increase of $0.04 per unit, or 12.5 percent, over the $0.32 distribution for the first quarter of 2007.

“We are excited to report that NuStar GP Holdings, LLC had record earnings and distributable cash flow in the first quarter of 2008. Looking forward, we continue to be well-positioned to benefit from further growth in cash distributions we receive from our ownership interests in NuStar Energy L.P., as we expect they will benefit from the completion of their terminal construction program and the acquisition of CITGO Asphalt Refining Company,” 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, April 22, 2008, to discuss the financial results for the first quarter of 2008. Investors interested in listening to the presentation may call 800/622-7620, passcode 42662979. International callers may access the presentation by dialing 706/645-0327, passcode 42662979. The company intends to have a playback available following the presentation, which may be accessed by calling 800/642-1687, passcode 42662979. A live broadcast of the conference call will also be available on the company’s Web site at www.nustargp.com. Further information on the conference call is provided in a management presentation posted to the NuStar Energy L.P. and NuStar GP Holdings, LLC Web sites at www.nustarenergy.com and www.nustargp.com in the Investors portion of the Web sites.

-More-

NuStar GP Holdings, LLC is a publicly traded limited liability company that owns the two percent general partner interest, a 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 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 partnership’s beliefs as well as assumptions made by and information currently available to the partnership. These statements reflect the partnership’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.

NuStar GP Holdings, LLC

Consolidated Financial Information

March 31, 2008 and 2007

(unaudited, thousands of dollars, except unit data and per unit data)

	Three Months Ended March 31,
	2008			2007
Statement of Income Data:
Equity in earnings of NuStar Energy L.P.	$	16,243		$	9,557
General and administrative expenses		(742	)		(796	)
Other expense, net		—			(26	)
Interest expense, net		(29	)		(4	)
Income before income tax benefit		15,472			8,731
Income tax benefit		20			40
Net income	$	15,492		$	8,771
Basic and diluted net income per unit	$	0.36		$	0.21
Equity in Earnings of NuStar Energy L.P.:
General partner interest (2%)	$	1,058		$	544
General partner incentive distribution		5,188			3,910
General partner’s interest in earnings of NuStar Energy L.P.		6,246			4,454
Limited partner interest in earnings of NuStar Energy L.P.		10,718			5,824
Amortization of step-up in basis related to NuStar Energy L.P.’s assets and liabilities		(721	)		(721	)
Equity in earnings of NuStar Energy L.P.	$	16,243		$	9,557
Distributable Cash Flow (Note 1):
Cash distributions from NuStar Energy L.P. associated with:
General partner interest (2%)	$	1,211		$	954
Incentive distribution rights (Note 2):		5,718			3,910
Limited partner interest-common units		10,067			9,359
Total cash distributions from NuStar Energy L.P.		16,996			14,223
Deduct expenses of NuStar GP Holdings, LLC:
General and administrative expenses		(742	)		(796	)
Income tax benefit		20			40
Interest expense, net		(29	)		(4	)
Distributable cash flow	$	16,245		$	13,463
Units outstanding		42,500,990			42,500,000
Distributable cash flow per unit	$	0.38		$	0.32
Cash distributions to be paid to the unitholders of NuStar GP Holdings, LLC:
Distribution per unit	$	0.36		$	0.32
Total distribution	$	15,300		$	13,600

NuStar GP Holdings, LLC

Consolidated Financial Information

March 31, 2008 and 2007

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

	Three Months Ended March 31,
	2008			2007
Net Income	$	15,492		$	8,771
Adjustments to derive Distributable Cash Flow:
Equity in earnings of NuStar Energy L.P.		(16,243	)		(9,557	)
Quarterly distribution from NuStar Energy L.P.		16,996			14,223
Other expense, net		—			26
Distributable Cash Flow		16,245			13,463
Adjustments to Distributable Cash Flow to derive Net Cash Provided by Operating Activities:
Quarterly distribution from NuStar Energy L.P.		(16,996	)		(14,223	)
Cash distribution of equity earnings received from NuStar Energy L.P.		16,243			9,557
Net effect of changes in operating accounts		(849	)		1,216
Net cash provided by operating activities	$	14,643		$	10,013

2. NuStar Energy L.P.’s net income allocation 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, will be greater than the net income allocation to the general partner.