Exhibit 99.1

NuStar Energy L.P. Reports Highest Quarterly Earnings in Partnership’s

History; Previously Announced Increase in Quarterly Distribution to $1.0575

Per Unit

SAN ANTONIO, October 23, 2008 – NuStar Energy L.P. (NYSE:NS) today announced record net income applicable to limited partners of $141.5 million, or $2.60 per unit, for the third quarter of 2008, almost three times higher than the $45.4 million, or $0.97 per unit, earned in the third quarter of 2007. The third quarter 2008 results represent the highest quarterly earnings in the partnership’s history – up $1.59 per unit over the previous quarterly record of $1.01 per unit earned in the first quarter of 2008. For the nine months ended September 30, 2008, net income applicable to limited partners was significantly higher at $199.3 million, or $3.78 per unit, compared to $106.6 million, or $2.28 per unit, for the nine months ended September 30, 2007.

With respect to the quarterly distribution to unitholders for the third quarter of 2008, NuStar Energy L.P. previously announced that its board of directors had increased the quarterly distribution rate to $1.0575 per unit, which would equate to $4.23 per unit on an annual basis. This quarterly distribution represents an increase of $0.0725 per unit, or 7.4 percent, over the $0.985 distribution for the second quarter of 2008 and third quarter of 2007 and will be paid on November 12, 2008, to holders of record as of November 5, 2008.

NuStar Energy L.P. also reported record quarterly distributable cash flow available to limited partners for the third quarter of 2008 of $156.4 million, or $2.87 per unit, or nearly 115 percent higher than the $62.7 million, or $1.34 per unit, for the third quarter of 2007. For the nine months ended September 30, 2008, distributable cash flow available to limited partners was also significantly higher at $259.9 million, or $4.91 per unit, compared to $163.7 million, or $3.50 per unit for the nine months ended September 30, 2007. Distributable cash flow available to limited partners covers the third quarter distribution to the limited partners by a strong 2.72 times.

“This was an outstanding quarter with earnings reaching an all-time quarterly high of $2.60 per unit, up over 165 percent versus the same period last year,” said Curt Anastasio, Chief Executive Officer and President of NuStar Energy L.P. and NuStar GP Holdings, LLC. “Our strong financial performance was primarily due to excellent margins and robust sales volumes on our asphalt operations, which were acquired in March. Within our asphalt and fuels marketing segment, our asphalt operations generated $122.5 million of operating income in the third quarter, or 63 percent of total segment operating income. With wide sour crude discounts and strong asphalt and intermediate product prices, our product margins averaged $16.05 per barrel.

-More-

“As a result of our strong financial results, we were able to provide a solid increase in the quarterly distribution of over seven percent to $1.0575 per unit. In addition, largely due to the excess cash flows generated from the asphalt operations and lower working capital needs, we reduced our debt balances during the third quarter by around $130 million. We currently have ample capacity under our $1.25 billion revolving credit facility with approximately $500 million available to us.

“Although we sustained property damage at our Texas City, Texas Terminal as a result of Hurricane Ike, estimated to be around $18 million, I am pleased to report that substantial repairs have already been made at this facility and we are making excellent progress toward a full recovery soon. The financial impact to us from Hurricane Ike is expected to be limited to our insurance deductible of $1 million.

“We continue to finish multiple projects on our $400 million construction program and expect to be complete with this program by May 2009. We only have around $40 million more in capital expenditures left under this program, which primarily includes storage expansion projects at Texas City, Texas; St. James, Louisiana and Amsterdam in the Netherlands. We completed around $150 million of projects in the third quarter of 2008, including storage expansion and pipeline optimization projects at St. James, Louisiana; Jacksonville, Florida; Linden, New Jersey (i.e. New York Harbor); Amsterdam and Texas City. When completed, we expect all of the projects under our $400 million construction program will contribute approximately $45 million of annual operating income.

“While we expect earnings for the fourth quarter of 2008 to be down significantly from the third quarter primarily due to the seasonality of the asphalt operations, the full year of 2008 should be a record year with the highest annual earnings in the partnership’s history. Longer-term, we expect that asphalt supply markets will continue to tighten and margins will increase as the refinery coker units come online. And, although we have identified approximately $500 million of high-return internal growth projects that could be completed over the next two to three years, we have scaled back our budgeted strategic and reliability capital expenditures in 2009 to approximately $150 million in light of the current capital markets environment,” said Anastasio.

-More-

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 and operational 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.nustarenergy.com.

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

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,
	2008			2007			2008			2007
Statement of Income Data:
Revenues:
Services revenues	$	187,104		$	188,677		$	547,775		$	511,970
Product sales		1,638,122			208,340			3,247,805			502,903
Total revenues		1,825,226			397,017			3,795,580			1,014,873
Costs and expenses:
Cost of product sales		1,467,152			199,023			3,036,077			475,011
Operating expenses		127,095			91,981			322,473			258,637
General and administrative expenses		20,358			16,118			55,985			48,607
Depreciation and amortization expense		35,143			29,534			100,019			84,736
Total costs and expenses		1,649,748			336,656			3,514,554			866,991
Operating income		175,478			60,361			281,026			147,882
Equity earnings from joint ventures		2,122			1,613			6,072			4,970
Interest expense, net		(25,228	)		(19,381	)		(67,027	)		(57,687	)
Other income, net		1,696			12,191			12,236			35,914
Income before income tax expense		154,068			54,784			232,307			131,079
Income tax expense		2,791			3,571			11,071			9,046
Net income		151,277			51,213			221,236			122,033
Less net income applicable to general partner (Note 1)		(9,817	)		(5,842	)		(21,904	)		(15,414	)
Net income applicable to limited partners	$	141,460		$	45,371		$	199,332		$	106,619
Income per unit applicable to limited partners (Note 1):	$	2.60		$	0.97		$	3.78		$	2.28
Weighted average number of basic units outstanding		54,460,549			46,809,749			52,753,696			46,809,749
EBITDA (Note 2)	$	214,439		$	103,699		$	399,353		$	273,502
Distributable cash flow (Note 2)	$	164,649		$	68,690		$	282,007		$	179,938
	September 30, 2008			September 30, 2007						December 31, 2007
Balance Sheet Data:
Debt, including current portion (a)	$	2,051,486		$	1,515,358					$	1,446,289
Partners’ equity (b)		2,266,187			1,873,168						1,994,832
Debt-to-capitalization ratio (a) / ((a)+(b))		47.5	%		44.7	%					42.0	%

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,
	2008			2007			2008			2007
Segment Data: (Note 3)
Storage:
Throughput (barrels/day)		713,323			844,511			756,319			802,622
Throughput revenues	$	22,640		$	26,069		$	68,790		$	71,771
Storage lease revenues		93,141			80,919			267,764			230,971
Total revenues		115,781			106,988			336,554			302,742
Operating expenses		68,699			58,214			183,818			167,019
Depreciation and amortization expense		16,900			15,886			49,548			46,322
Segment operating income	$	30,182		$	32,888		$	103,188		$	89,401
Transportation:
Refined products pipelines throughput (barrels/day)		652,174			719,385			682,214			661,709
Crude oil pipelines throughput (barrels/day)		398,341			410,758			405,276			369,184
Total throughput (barrels/day)		1,050,515			1,130,143			1,087,490			1,030,893
Revenues	$	81,163		$	83,900		$	233,970		$	214,928
Operating expenses		39,543			32,677			99,873			89,609
Depreciation and amortization expense		12,659			12,825			38,061			37,591
Segment operating income	$	28,961		$	38,398		$	96,036		$	87,728
Asphalt and fuels marketing:
Product sales	$	1,638,122		$	208,340		$	3,247,834		$	502,903
Cost of product sales		1,471,084			200,182			3,046,755			478,274
Operating expenses		24,770			2,142			50,848			4,446
Depreciation and amortization expense		4,664			68			9,872			68
Segment operating income	$	137,604		$	5,948		$	140,359		$	20,115
Consolidation and intersegment eliminations:
Revenues	$	(9,840	)	$	(2,211	)	$	(22,778	)	$	(5,700	)
Cost of product sales		(3,932	)		(1,159	)		(10,678	)		(3,263	)
Operating expenses		(5,917	)		(1,052	)		(12,066	)		(2,437	)
Depreciation and amortization expense		920			755			2,538			755
Total	$	(911	)	$	(755	)	$	(2,572	)	$	(755	)
Consolidated Information:
Revenues	$	1,825,226		$	397,017		$	3,795,580		$	1,014,873
Cost of product sales		1,467,152			199,023			3,036,077			475,011
Operating expenses		127,095			91,981			322,473			258,637
Depreciation and amortization expense		35,143			29,534			100,019			84,736
Segment operating income		195,836			76,479			337,011			196,489
General and administrative expenses		20,358			16,118			55,985			48,607
Consolidated operating income	$	175,478		$	60,361		$	281,026		$	147,882

NuStar Energy L.P. and Subsidiaries

Consolidated Financial Information - Continued

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

Notes:

1. 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 September 30,						Nine Months Ended September 30,
	2008			2007			2008			2007
Net income applicable to general partner and limited partners’ interest	$	151,277		$	51,213		$	221,236		$	122,033
Less general partner incentive distribution		6,929			4,915			17,835			13,238
Net income after general partner incentive distribution		144,348			46,298			203,401			108,795
General partner interest		2	%		2	%		2	%		2	%
General partner allocation of net income after general partner incentive distribution		2,888			927			4,069			2,176
General partner incentive distribution		6,929			4,915			17,835			13,238
Net income applicable to general partner	$	9,817		$	5,842		$	21,904		$	15,414

2. 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,
	2008			2007			2008			2007
Net income	$	151,277		$	51,213		$	221,236		$	122,033
Plus interest expense, net		25,228			19,381			67,027			57,687
Plus income tax expense		2,791			3,571			11,071			9,046
Plus depreciation and amortization expense		35,143			29,534			100,019			84,736
EBITDA		214,439			103,699			399,353			273,502
Less equity earnings from joint ventures		(2,122	)		(1,613	)		(6,072	)		(4,970	)
Less interest expense, net		(25,228	)		(19,381	)		(67,027	)		(57,687	)
Less reliability capital expenditures		(11,083	)		(11,597	)		(28,001	)		(23,558	)
Less income tax expense		(2,791	)		(3,571	)		(11,071	)		(9,046	)
Plus distributions from joint ventures		—			—			500			544
Mark-to-market impact on hedge transactions (a)		(8,566	)		1,153			(5,675	)		1,153
Distributable cash flow		164,649			68,690			282,007			179,938
General partner’s interest in distributable cash flow		(8,247	)		(5,956	)		(22,105	)		(16,230	)
Limited partners’ interest in distributable cash flow	$	156,402		$	62,734		$	259,902		$	163,708
Distributable cash flow per limited partner unit	$	2.872		$	1.340		$	4.908		$	3.497

(a) Distributable cash flow excludes the impact of mark-to-market gains and losses which arise from valuing certain derivative contracts.

3. Beginning in the second quarter of 2008, we changed the way we report our segmental results. We combined the refined product terminals and crude oil storage tanks segments into the storage segment, and we combined the refined product pipelines and crude oil pipelines segments into the transportation segment. Previous periods have been restated to conform to this presentation. The asphalt and fuels marketing segment includes all product sales and related costs, including our two asphalt refineries, which we acquired on March 20, 2008. Additional operational information related to the asphalt and fuels marketing segment is available on our website at www.nustarenergy.com under the investors portion of the website.