Exhibit 99.1

NuStar Energy L.P. Reports First Quarter 2010 Earnings and Announces

Quarterly Distribution

Higher 2010 Earnings Still Expected For the Remainder of the Year Due to Improved Results from Asphalt Operations and Internal Growth Projects in the Storage Segment

SAN ANTONIO, April 29, 2010 – NuStar Energy L.P. (NYSE: NS) today announced distributable cash flow available to limited partners of $22.8 million, or $0.38 per unit, for the first quarter of 2010 compared to $69.4 million, or $1.28 per unit, for the same period in 2009. Earnings before interest, taxes, depreciation and amortization (EBITDA) were $81.0 million for the first quarter of 2010 compared to $102.3 million for the first quarter of 2009. Net income applicable to limited partners was $11.5 million, or $0.19 per unit, for the first quarter of 2010, compared to $31.6 million, or $0.58 per unit, earned in the first quarter of 2009.

The first quarter 2009 results include a $4.7 million, or $0.08 per unit gain, net of tax, related to property insurance proceeds received due to damage caused by Hurricane Ike that occurred at the Texas City, Texas terminal in the third quarter of 2008. Excluding the effect of the insurance proceeds and other items, first quarter 2009 adjusted net income applicable to limited partners would have been $25.8 million, or $0.47 per unit.

NuStar Energy L.P. also announced that its board of directors has declared a distribution of $1.065 per unit for the first quarter of 2010, which would equate to $4.26 per unit on an annual basis. This cash distribution will be paid on May 14, 2010, to holders of record as of May 7, 2010, and represents an increase over the $1.0575 per unit distribution for the first quarter of 2009.

“First quarter 2010 earnings were in-line with the $80 to $100 million EBITDA guidance we had provided in the last quarterly earnings conference call in late January,” said Curt Anastasio, Chief Executive Officer and President of NuStar Energy L.P. and NuStar GP Holdings, LLC. “Earnings were at the lower end of the range reflective of the seasonal weakness that occurs during this time of the year when sales and throughput volumes taper off, but eventually ramp up in the second and third quarters as the asphalt, summer-driving and agricultural seasons start up. Compared to last year, we generated higher top-line results in each of our three business segments mainly due to higher tariffs in our transportation segment, the completion of growth projects and higher renewal rates in our storage segment and improved sales volumes and higher sales prices in our asphalt operations.

-More-

“For the remainder of 2010, we continue to expect results to improve as the asphalt season gets underway, refined product demand continues to pick up and internal growth projects start contributing to earnings. For the full year of 2010, we are projecting that EBITDA will be higher than 2009 and we still plan to recommend to our Board an increase in the distribution this year.

Asphalt and Fuels Marketing Segment Expected to Perform Better in 2010 - Asphalt Fundamentals Looking Favorable This Year; Well-Positioned for Asphalt Supply Gap Expected to Occur from New Coker Projects Coming On-Line

“Our view on our asphalt and fuels marketing segment in 2010 has not changed and reflects an improved outlook compared to last year’s results. We are currently projecting full year 2010 adjusted EBITDA from this segment to be higher than the $80 million earned last year.

“With respect to our asphalt operations, asphalt demand should be comparable to last year as higher stimulus spending and an improving economy will be contributing factors during this year’s asphalt season. On the supply-side, asphalt inventories continue to be at historic lows as reduced refinery utilization rates, higher than normal refinery turnarounds and lack of asphalt imports continue to limit asphalt supplies. We continue to believe that new coker projects will contribute to the further tightening of asphalt supply starting in 2011 and 2012, and we are well-positioned to capture incremental margins from the expected supply gap.

Continue to see Better Results from our Fee-Based Storage Segment and Relatively Stable Results from our Fee-Based Transportation Segment

“Our full year 2010 forecast for the storage segment reflects adjusted EBITDA that is approximately $12 to $16 million higher than the $242 million of adjusted EBITDA generated in 2009. The storage segment should continue to benefit from higher renewal rates in some of our markets and internal growth projects completed late in 2009 and during 2010.

“We continue to expect throughput volumes on our transportation segment will be higher in 2010 compared to 2009, or around one to two percent better, excluding the impact of the pipeline assets sales completed in the second quarter of last year,” said Anastasio. This is mainly due to an improving economy and, consequently a recovery in refined product demand. In addition, we should benefit from a higher revenue per barrel rate in 2010, even though tariff rates on interstate pipelines are expected to decline an estimated 1.2 percent starting July 1, 2010 as part of the pipeline index established by the Federal Energy Regulatory Commission. Also, as we have stated in our earlier guidance, increased operating expenses due to higher power, maintenance and other operating costs in 2010 should be an offset to our higher revenues, however, we expect the financial impact will be minimal causing adjusted EBITDA to be comparable to slightly lower compared to last year.”

-More-

Expect Significantly Improved Results for the Second Quarter of 2010

“For the second quarter of 2010, we are projecting EBITDA to be in the range of $130 to $150 million. This is primarily due to our expectations for better results from our asphalt and fuels marketing segment as the asphalt season should start to ramp up during the second quarter,” said Anastasio.

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

NuStar Energy L.P. is a publicly traded, limited partnership based in San Antonio, with 8,417 miles of pipeline, 86 terminal 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 91 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 and company’s beliefs as well as assumptions made by and information currently available to the partnership and company. These statements reflect the partnership and 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 Energy L.P. and NuStar GP Holdings, LLC’s 2009 annual reports on Form 10-K and subsequent filings with the Securities and Exchange Commission.

-30-

NuStar Energy L.P. and Subsidiaries

Consolidated Financial Information

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

	Three Months Ended March 31,
	2010			2009
Statement of Income Data:
Revenues:
Service revenues	$	189,295		$	182,652
Product sales		756,234			451,352
Total revenues		945,529			634,004
Costs and expenses:
Cost of product sales		719,221			416,795
Operating expenses		121,337			103,322
General and administrative expenses		27,269			22,464
Depreciation and amortization expense		37,929			35,989
Total costs and expenses		905,756			578,570
Operating income		39,773			55,434
Equity earnings from joint ventures		3,015			2,313
Interest expense, net		(18,586	)		(20,470	)
Other income, net		301			8,604
Income before income tax expense		24,503			45,881
Income tax expense		4,800			6,526
Net income	$	19,703		$	39,355
Net income applicable to limited partners	$	11,511		$	31,638
Net income per unit applicable to limited partners	$	0.19		$	0.58
Weighted average limited partner units outstanding		60,210,549			54,460,549
EBITDA (Note 1)	$	81,018		$	102,340
Distributable cash flow (Note 1)	$	32,049		$	77,684
	March 31, 2010			December 31, 2009
Balance Sheet Data:
Debt, including current portion (a)	$	1,898,107		$	1,849,763
Partners’ equity (b)		2,430,330			2,484,968
Debt-to-capitalization ratio (a) / ((a)+(b))		43.9	%		42.7	%

NuStar Energy L.P. and Subsidiaries

Consolidated Financial Information - Continued

(Unaudited, Thousands of Dollars, Except Barrel Data)

	Three Months Ended March 31,
	2010			2009
Segment Data:
Storage:
Throughput (barrels/day)		641,457			595,943
Throughput revenues	$	17,827		$	20,028
Storage lease revenues		108,805			97,774
Total revenues		126,632			117,802
Operating expenses		65,078			54,158
Depreciation and amortization expense		18,666			16,992
Segment operating income	$	42,888		$	46,652
Transportation:
Refined products pipelines throughput (barrels/day)		527,340			620,223
Crude oil pipelines throughput (barrels/day)		363,237			385,984
Total throughput (barrels/day)		890,577			1,006,207
Revenues	$	75,262		$	74,392
Operating expenses		28,753			25,200
Depreciation and amortization expense		12,752			12,663
Segment operating income	$	33,757		$	36,529
Asphalt and fuels marketing:
Product sales	$	758,930		$	451,352
Cost of product sales		726,734			420,793
Gross margin		32,196			30,559
Operating expenses		35,051			29,839
Depreciation and amortization expense		5,041			5,208
Segment operating income (loss)	$	(7,896	)	$	(4,488	)
Consolidation and intersegment eliminations:
Revenues	$	(15,295	)	$	(9,542	)
Cost of product sales		(7,513	)		(3,998	)
Operating expenses		(7,545	)		(5,875	)
Total	$	(237	)	$	331
Consolidated Information:
Revenues	$	945,529		$	634,004
Cost of product sales		719,221			416,795
Operating expenses		121,337			103,322
Depreciation and amortization expense		36,459			34,863
Segment operating income		68,512			79,024
General and administrative expenses		27,269			22,464
Other depreciation and amortization expense		1,470			1,126
Consolidated operating income	$	39,773		$	55,434

NuStar Energy L.P. and Subsidiaries

Consolidated Financial Information - Continued

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

Notes:

1. 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,
	2010			2009
Net income	$	19,703		$	39,355
Plus interest expense, net		18,586			20,470
Plus income tax expense		4,800			6,526
Plus depreciation and amortization expense		37,929			35,989
EBITDA		81,018			102,340
Less equity earnings from joint ventures		(3,015	)		(2,313	)
Less interest expense, net		(18,586	)		(20,470	)
Less reliability capital expenditures		(12,355	)		(5,942	)
Less income tax expense		(4,800	)		(6,526	)
Plus distributions from joint ventures		2,400			1,500
Mark-to-market impact on hedge transactions (a)		(12,613	)		9,095
Distributable cash flow		32,049			77,684
General partner’s interest in distributable cash flow		(9,266	)		(8,247	)
Limited partners’ interest in distributable cash flow	$	22,783		$	69,437
Distributable cash flow per limited partner unit	$	0.378		$	1.275

(a) Distributable cash flow excludes the impact of unrealized mark-to-market gains and losses which arise from valuing certain derivative contracts that hedge a portion of our inventory but do not qualify for hedge accounting treatment. The gain or loss associated with these contracts is realized in distributable cash flow when the contracts are settled.