Press Release

Exhibit 99.1

NuStar Energy L.P. Reports Record First Quarter 2008 Earnings and

Announces Quarterly Distribution

SAN ANTONIO, April 22, 2008 – NuStar Energy L.P. (NYSE:NS) today announced net income applicable to limited partners of $51.8 million, or $1.05 per unit, for the first quarter of 2008, nearly double the $26.7 million, or $0.57 per unit, earned in the first quarter of 2007. The partnership’s first quarter 2008 results represent the highest quarterly earnings in the partnership’s history.

Included in the first quarter 2008 results in other income is a $4.3 million gain, or $0.08 per unit, for the sale of an idle refined products pipeline; $3.3 million of income, or $0.06 per unit, related to settlement of the business interruption insurance claim for the impact of the fire at Valero Energy’s McKee refinery last year; and $1.8 million, or $0.04 per unit, related to a non-cash foreign exchange gain on U.S. dollars held by our Canadian subsidiary. Excluding the impact of these and other items, adjusted earnings for the first quarter of 2008 would have been $43.8 million, or $0.89 per unit, which still represents the highest first quarter earnings in the partnership’s history.

Distributable cash flow available to limited partners for the first quarter of 2008 was $70.3 million, or $1.42 per unit, compared to $47.4 million, or $1.01 per unit, for the first quarter of 2007. Distributable cash flow available to limited partners covers the distribution to the limited partners by 1.44 times for the first quarter of 2008.

With respect to the quarterly distribution to unitholders for the first quarter of 2008, NuStar also announced that its board of directors has declared a distribution of $0.985 per unit, or $3.94 per unit on an annual basis, which will be paid on May 14, 2008, to holders of record as of May 7, 2008.

“2008 is off to a great start with the highest quarterly earnings in the partnership’s history,” said Curt Anastasio, Chief Executive Officer and President of NuStar Energy L.P. and NuStar GP Holdings, LLC. “During the quarter, we benefited from increased throughputs on our pipelines and terminals serving Valero Energy’s McKee refinery, higher storage lease and throughput revenues on several of our refined product terminals and a higher contribution from our marketing and trading businesses, which started up in the second quarter of last year. With the remainder of the projects on our $400 million construction program expected to be in service during the year and the recent completion of the CITGO Asphalt Refining Company acquisition, 2008 is shaping up to be an exciting year for NuStar.

-More-

“With respect to our recent acquisition of CITGO Asphalt Refining Company, which we closed on March 20 near the end of the first quarter, we continue to expect these assets will be a significant contributor to our distributable cash flow in 2008, particularly in the second and third quarters during the asphalt paving season.

“Our employees have done a terrific job integrating these assets in the short time that we have owned them and I am very pleased with the quality of the assets, the management team and the employees. We are in a great position to build upon the asset base having identified around $35 million of high-return, quick pay-back projects at both the Paulsboro and Savannah refineries that can be implemented in the next six to 24 months. Most of these are projects that focus on allowing greater flexibility to run different crude oil qualities at the refineries. Other projects focus on increasing the energy efficiency of the refineries, increasing the production of the higher quality, higher value polymer modified asphalt and improving the yields and quality of roofing flux and intermediate products. Longer term, we continue to evaluate other projects that focus on the increased flexibility to diminish our exposure to the seasonality of the asphalt business and increase refinery throughput in the off season.

“Looking ahead to the second quarter of 2008, we expect to benefit from the recently acquired asphalt business as asphalt margins should recover from weak first quarter levels. These increasing margins are driven by seasonal asphalt demand ramping up during the second quarter, as well as low inventory levels on the U.S. East Coast compared to last year,” said Anastasio.

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 and operational 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.nustarenergy.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 Energy L.P. is a publicly traded, limited partnership based in San Antonio, with 9,063 miles of pipeline, 85 terminal facilities, four crude oil storage tank facilities and two asphalt refineries with a combined throughput capacity of 104,000 barrels per day. One of the largest asphalt refiners and marketers in the U.S. and the second largest independent liquids terminal operator in the nation, NuStar has operations in the United States, the Netherlands Antilles, Canada, Mexico, the Netherlands and the United Kingdom. The partnership’s combined system has over 86 million barrels of storage capacity, and includes two asphalt refineries, crude oil and refined product pipelines, refined product terminals, a petroleum and specialty liquids storage and terminaling business, as well as crude oil storage facilities. For more information, visit NuStar Energy L.P.’s Web site at www.nustarenergy.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 Energy L.P.’s 2007 annual report on Form 10-K and subsequent filings with the Securities and Exchange Commission.

-More-

NuStar Energy L.P.

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:
Revenues:
Service revenues	$	180,326		$	160,353
Product sales		412,658			136,471

Total revenues		592,984			296,824
Costs and expenses:
Cost of product sales		389,284			127,927
Operating expenses		89,507			81,212
General and administrative expenses		16,321			14,908
Depreciation and amortization expense		30,276			27,342

Total costs and expenses		525,388			251,389

Operating income		67,596			45,435
Equity earnings from joint ventures		2,249			1,611
Interest expense, net		(16,902	)		(18,854	)
Other income, net		9,684			6,623

Income before income tax expense		62,627			34,815
Income tax expense		4,562			3,692

Net income		58,065			31,123
Less net income applicable to general partner (Note 1)		(6,246	)		(4,454	)

Net income applicable to limited partners	$	51,819		$	26,669

Net income per unit applicable to limited partners (Note 1)	$	1.05		$	0.57

Weighted average number of basic units outstanding		49,409,749			46,809,749
EBITDA (Note 2)	$	109,805		$	81,011
Distributable cash flow (Note 2)	$	77,262		$	52,228

	March 31, 2008			December 31, 2007
Balance Sheet Data:
Debt, including current portion (a)	$	2,203,299		$	1,446,289
Partners’ equity (b)		1,994,644			1,994,832
Debt-to-capitalization ratio (a) / ((a)+(b))		52.5	%		42.0	%

NuStar Energy L.P.

Consolidated Financial Information - Continued

March 31, 2008 and 2007

(unaudited, thousands of dollars, except barrel information)


	Three Months Ended March 31,
	2008			2007
Operating Data:
Refined product terminals: (Note 3)
Throughput (barrels/day)		291,762			241,774
Throughput revenues	$	13,498		$	11,737
Storage lease revenues		83,918			73,864

Total revenues		97,416			85,601
Operating expenses		52,459			50,810
Depreciation and amortization expense		14,021			13,188

Segment operating income	$	30,936		$	21,603

Refined product pipelines: (Note 3)
Throughput (barrels/day)		694,772			616,728
Revenues	$	60,745		$	53,424
Operating expenses		26,179			24,365
Depreciation and amortization expense		11,368			11,008

Segment operating income	$	23,198		$	18,051

Crude oil pipelines:
Throughput (barrels/day)		405,964			347,617
Revenues	$	15,034		$	12,349
Operating expenses		3,939			3,373
Depreciation and amortization expense		1,237			1,233

Segment operating income	$	9,858		$	7,743

Crude oil storage tanks:
Throughput (barrels/day)		503,489			539,214
Revenues	$	11,907		$	10,813
Operating expenses		2,335			2,770
Depreciation and amortization expense		1,930			1,913

Segment operating income	$	7,642		$	6,130

Refining and marketing: (Note 3)
Product sales	$	412,658		$	136,471
Cost of product sales		392,457			129,043
Operating expenses		6,218			612
Depreciation and amortization expense		918			—

Segment operating income	$	13,065		$	6,816

Consolidation and intersegment eliminations:
Revenues	$	(4,776	)	$	(1,834	)
Cost of product sales		(3,173	)		(1,116	)
Operating expenses		(1,623	)		(718	)
Depreciation and amortization expense		802			—

Total	$	(782	)	$	—

Consolidated information:
Revenues	$	592,984		$	296,824
Cost of product sales		389,284			127,927
Operating expenses		89,507			81,212
Depreciation and amortization expense		30,276			27,342

Segment operating income		83,917			60,343
General and administrative expenses		16,321			14,908

Consolidated operating income	$	67,596		$	45,435

NuStar Energy L.P.

Consolidated Financial Information - Continued

March 31, 2008 and 2007

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

Notes:

Net income is allocated between limited partners and the general partner’s interests based on provisions in the partnership agreement. The net income applicable to limited partners is divided by the weighted average number of limited partnership units outstanding in computing the net income per unit applicable to limited partners. The following table details the calculation of net income applicable to the general partner:


	Three Months Ended March 31,
	2008			2007
Net income applicable to general partner and limited partners’ interest	$	58,065		$	31,123
General partner incentive distribution		5,188			3,910

Net income after general partner incentive distribution		52,877			27,213
General partner interest		2	%		2	%

General partner allocation of net income after general partner incentive distribution		1,058			544
General partner incentive distribution		5,188			3,910

Net income applicable to general partner	$	6,246		$	4,454

NuStar Energy L.P. utilizes two financial measures, EBITDA and distributable cash flow, which are not defined in United States generally accepted accounting principles. Management uses these financial measures because they are widely accepted financial indicators used by investors to compare partnership performance. In addition, management believes that these measures provide investors an enhanced perspective of the operating performance of the partnership’s assets and the cash that the business is generating. Neither EBITDA nor distributable cash flow are intended to represent cash flows for the period, nor are they presented as an alternative to net income. They 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 EBITDA and distributable cash flow:


	Three Months Ended March 31,
	2008			2007
Net income	$	58,065		$	31,123
Plus interest expense, net		16,902			18,854
Plus income tax expense		4,562			3,692
Plus depreciation and amortization expense		30,276			27,342

EBITDA		109,805			81,011
Less equity earnings from joint ventures		(2,249	)		(1,611	)
Less interest expense, net		(16,902	)		(18,854	)
Less reliability capital expenditures		(7,369	)		(4,626	)
Less income tax expense		(4,562	)		(3,692	)
Plus distributions from joint ventures		500			—
Mark-to-market impact on hedge transactions (a)		(1,961	)		—

Distributable cash flow		77,262			52,228

General partner’s interest in distributable cash flow		(6,929	)		(4,864	)

Limited partners’ interest in distributable cash flow	$	70,333		$	47,364

Weighted average number of limited partnership units outstanding		49,409,749			46,809,749

Distributable cash flow per limited partner unit	$	1.423		$	1.012
(a) Distributable cash flow excludes the impact of mark-to-market gains and losses which arise from valuing certain derivative contracts that are considered economic hedges. We enter into these contracts to mitigate our exposure to price fluctuations related to our inventory.

The refining and marketing segment includes our two asphalt refineries, which we acquired on March 20, 2008, as well as our marketing and trading operations. During the fourth quarter of 2007, we revised the manner in which we internally evaluate our segment performance and made certain organizational changes. As a result, we changed the way we report our segmental information such that all product sales and related costs and assets are included in the refining and marketing segment. Previous periods have been restated to conform to this presentation.