Exhibit 99.1

NuStar Energy L.P. Reports Higher than Anticipated Third Quarter 2010

Earnings and Increases Quarterly Distribution

2010 Fourth Quarter and Full Year results expected to be higher than 2009

SAN ANTONIO, October 25, 2010 – NuStar Energy L.P. (NYSE: NS) today announced distributable cash flow available to limited partners for the third quarter of $84.0 million, or $1.30 per unit, compared to 2009 third quarter distributable cash flow of $61.5 million, or $1.13 per unit.

The partnership also announced that its board of directors has declared a third quarter 2010 distribution of $1.075 per unit, which is $0.01 per unit or approximately 1% higher than the second quarter 2010 and third quarter 2009 distributions of $1.065 per unit. The third quarter 2010 distribution will be paid on November 5, 2010, to holders of record as of November 1, 2010. Distributable cash flow available to limited partners covers the distribution to the limited partners by 1.21 times for the third quarter of 2010.

NuStar Energy L.P. reported third quarter net income applicable to limited partners of $58.4 million, or $0.90 per unit, compared to $56.1 million, or $1.03 per unit, earned in the third quarter of 2009. Earnings before interest, taxes, depreciation and amortization (EBITDA) were $131.0 million for the third quarter of 2010 compared to $124.4 million for the third quarter of 2009.

“I am excited to announce that our third quarter results were better than we expected when earnings guidance was provided in early August,” said Curt Anastasio, Chief Executive Officer and President of NuStar Energy L.P. and NuStar GP Holdings, LLC. “Higher than projected throughputs on our crude, refined products and ammonia pipelines and improved asphalt margins in our asphalt and fuels marketing segment caused our results to be higher than anticipated.”

“I am particularly pleased that, all three of our business segments generated higher operating income and EBITDA in the third quarter of 2010 and for the nine months ended September 30, 2010 when compared to the same periods in 2009. As a result of these strong results, we were able to increase our third quarter 2010 distribution,” said Anastasio.

-More-

Fourth Quarter and Full-Year 2010 EBITDA Projected to be Higher than 2009

“For the fourth quarter of 2010, we are projecting EBITDA to be in the range of $110 to $130 million, which would be the highest fourth quarter in our history and $20 to $40 million higher than the fourth quarter of 2009. Incremental EBITDA from internal growth projects coming online in the storage segment, additional profits attributable to the Mobile County, Alabama storage terminal acquisition that was completed in May 2010, and increased earnings from our fuels marketing operations will contribute to increased EBITDA in the fourth quarter of 2010,” said Anastasio.

Commenting on the full-year outlook for the fee-based storage and transportation business segments, Anastasio said, “We expect incremental EBITDA in our storage segment to be $14 to $18 million higher than 2009. This is lower than previous guidance largely because the start-up of one of our internal growth projects has been delayed by approximately 30 days and vessel activity at our St. Eustatius terminal has been negatively impacted by tropical storms during the third quarter. The good news is that EBITDA in our transportation segment is now projected to be $5 to $10 million higher than 2009 due to higher throughputs and a customer turnaround being delayed until 2011.”

In regard to the margin-based asphalt and fuels marketing segment Anastasio added, “Improving asphalt margins in the third and fourth quarters of 2010 as well as continued strong earnings results in our fuels marketing operations should cause EBITDA in this segment to be $25 to $35 million higher than the $80 million of EBITDA earned last year.”

Turkey Terminal Acquisition

“We expect to close our previously announced $50 to $60 million acquisition of a 75% controlling interest in a joint venture in Mersin, Turkey in December 2010. The joint venture will own two terminals with a storage capacity of 1.3 million barrels, a two-thirds interest in an off-shore ship platform, and land that can be used for the construction of additional terminal operations. The transaction is expected to be immediately accretive to NuStar Energy’s distributable cash flow per unit,” said Anastasio.

Eagle Ford Shale Project

“Last week NuStar and Koch Pipeline Company reached agreement on a pipeline connection and capacity lease agreement. Under this agreement, NuStar will reactivate a previously idled pipeline in South Texas that will now be utilized to transport Eagle Ford Shale crude oil production to Corpus Christi, Texas refineries and terminals. We expect this project to be completed and in service in the second quarter of 2011,” stated Anastasio.

“With the EBITDA benefits from our large strategic capital spending program and our upcoming Turkey terminal acquisition, EBITDA and distributable cash flow growth should continue into 2011 and beyond,” said Anastasio.

A conference call with management is scheduled for 3:00 p.m. ET (2:00 p.m. CT) today, October 25, 2010, to discuss the financial and operational results for the third quarter of 2010. Investors interested in listening to the presentation may call 800/622-7620, passcode 12873811. International callers may access the presentation by dialing 706/645-0327, passcode 12873811. The company intends to have a playback available following the presentation, which may be accessed by calling 800/642-1687, passcode 12873811. 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; 88 terminal and storage facilities that store and distribute crude oil, refined products and specialty liquids; and two asphalt refineries with a combined throughput capacity of 104,000 barrels per day. The partnership’s combined system has over 93 million barrels of storage capacity. 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. For more information, visit NuStar Energy L.P.’s Web site at www.nustarenergy.com.

This release serves as qualified notice to nominees under Treasury Regulation Sections 1.1446-4(b)(4) and (d). Please note that 100% of NuStar’s distributions to foreign investors are attributable to income that is effectively connected with a United States trade or business. Accordingly, all of NuStar’s distributions to foreign investors are subject to federal income tax withholding at the highest effective tax rate for individuals and corporations, as applicable. Nominees, and not NuStar, are treated as the withholding agents responsible for withholding on the distributions received by them on behalf of foreign investors.

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.

NuStar Energy L.P. and Subsidiaries

Consolidated Financial Information

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

	Three Months Ended September 30,						Nine Months Ended September 30,
	2010			2009			2010			2009
Statement of Income Data:
Revenues:
Services revenues	$	201,390		$	190,439		$	585,772		$	549,133
Product sales		936,989			1,060,808			2,623,077			2,323,960
Total revenues		1,138,379			1,251,247			3,208,849			2,873,093
Costs and expenses:
Cost of product sales		860,942			989,868			2,422,751			2,138,524
Operating expenses		121,748			118,190			363,028			332,017
General and administrative expenses		26,860			19,213			76,324			67,529
Depreciation and amortization expense		38,539			36,786			114,653			108,323
Total costs and expenses		1,048,089			1,164,057			2,976,756			2,646,393
Operating income		90,290			87,190			232,093			226,700
Equity earnings from joint venture		2,454			2,374			7,571			7,698
Interest expense, net		(20,583	)		(19,791	)		(58,059	)		(60,526	)
Other (expense) income, net		(235	)		(1,961	)		14,882			25,883
Income before income tax expense		71,926			67,812			196,487			199,755
Income tax expense		3,616			3,372			9,052			12,225
Net income	$	68,310		$	64,440		$	187,435		$	187,530
Net income applicable to limited partners	$	58,375		$	56,097		$	158,950		$	162,865
Net income per unit applicable to limited partners	$	0.90		$	1.03		$	2.55		$	2.99
Weighted average limited partner units outstanding		64,610,549			54,460,549			62,386,373			54,460,549
EBITDA (Note 1)	$	131,048		$	124,389		$	369,199		$	368,604
Distributable cash flow (Note 1)	$	94,202		$	69,920		$	243,372		$	279,292
	September 30, 2010			September 30, 2009						December 31, 2009
Balance Sheet Data:
Debt, including current portion (a)	$	1,990,507		$	1,925,792					$	1,849,763
Partners’ equity (b)		2,690,235			2,217,240						2,484,968
Debt-to-capitalization ratio (a) / ((a)+(b))		42.5	%		46.5	%					42.7	%

NuStar Energy L.P. and Subsidiaries

Consolidated Financial Information - Continued

(Unaudited, Thousands of Dollars, Except Barrel Data)

	Three Months Ended September 30,						Nine Months Ended September 30,
	2010			2009			2010			2009
Segment Data:
Storage:
Throughput (barrels/day)		673,121			708,281			666,635			667,005
Throughput revenues	$	19,139		$	19,892		$	56,085		$	59,648
Storage lease revenues		111,998			105,341			330,493			300,700
Total revenues		131,137			125,233			386,578			360,348
Operating expenses		66,153			63,166			198,186			176,794
Depreciation and amortization expense		19,349			18,034			57,004			52,472
Segment operating income	$	45,635		$	44,033		$	131,388		$	131,082
Transportation:
Refined products pipelines throughput (barrels/day)		526,825			544,345			529,380			576,165
Crude oil pipelines throughput (barrels/day)		382,845			318,567			381,606			350,034
Total throughput (barrels/day)		909,670			862,912			910,986			926,199
Revenues	$	80,597		$	78,015		$	232,817		$	221,151
Operating expenses		30,488			29,966			88,784			82,856
Depreciation and amortization expense		12,597			12,624			38,029			37,901
Segment operating income	$	37,512		$	35,425		$	106,004		$	100,394
Asphalt and fuels marketing:
Product sales	$	937,074		$	1,060,808		$	2,625,994		$	2,323,960
Cost of product sales		864,904			993,648			2,438,703			2,150,450
Gross margin		72,170			67,160			187,291			173,510
Operating expenses		31,575			34,128			96,924			93,676
Depreciation and amortization expense		5,138			4,922			15,254			14,536
Segment operating income	$	35,457		$	28,110		$	75,113		$	65,298
Consolidation and intersegment eliminations:
Revenues	$	(10,429	)	$	(12,809	)	$	(36,540	)	$	(32,366	)
Cost of product sales		(3,962	)		(3,780	)		(15,952	)		(11,926	)
Operating expenses		(6,468	)		(9,070	)		(20,866	)		(21,309	)
Total	$	1		$	41		$	278		$	869
Consolidated Information:
Revenues	$	1,138,379		$	1,251,247		$	3,208,849		$	2,873,093
Cost of product sales		860,942			989,868			2,422,751			2,138,524
Operating expenses		121,748			118,190			363,028			332,017
Depreciation and amortization expense		37,084			35,580			110,287			104,909
Segment operating income		118,605			107,609			312,783			297,643
General and administrative expenses		26,860			19,213			76,324			67,529
Other depreciation and amortization expense		1,455			1,206			4,366			3,414
Consolidated operating income	$	90,290		$	87,190		$	232,093		$	226,700

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 September 30,						Nine Months Ended September 30,
	2010			2009			2010			2009
Net income	$	68,310		$	64,440		$	187,435		$	187,530
Plus interest expense, net		20,583			19,791			58,059			60,526
Plus income tax expense		3,616			3,372			9,052			12,225
Plus depreciation and amortization expense		38,539			36,786			114,653			108,323
EBITDA		131,048			124,389			369,199			368,604
Less equity earnings from joint ventures		(2,454	)		(2,374	)		(7,571	)		(7,698	)
Less interest expense, net		(20,583	)		(19,791	)		(58,059	)		(60,526	)
Less reliability capital expenditures		(13,841	)		(16,424	)		(38,327	)		(32,915	)
Less income tax expense		(3,616	)		(3,372	)		(9,052	)		(12,225	)
Plus distributions from joint venture		2,450			2,750			7,500			6,750
Mark-to-market impact on hedge transactions (a)		1,198			(15,258	)		(20,318	)		17,302
Distributable cash flow		94,202			69,920			243,372			279,292
General partner’s interest in distributable cash flow		(10,160	)		(8,382	)		(29,371	)		(24,876	)
Limited partners’ interest in distributable cash flow	$	84,042		$	61,538		$	214,001		$	254,416
Distributable cash flow per limited partner unit	$	1.30		$	1.13		$	3.40		$	4.67

(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.