Exhibit 99.1

NuStar Energy L.P. Reports Fourth Quarter and Full Year 2009 Earnings

and Announces Quarterly Distribution

2009 Net Income and EBITDA Second Highest in Partnership’s History

Stronger Fourth Quarter 2009 Results Compared to the Same Period Last Year Due to Much

Improved Asphalt Results

SAN ANTONIO, January 29, 2010 – NuStar Energy L.P. (NYSE: NS) today announced distributable cash flow available to limited partners of $57.0 million, or $0.99 per unit, for the fourth quarter of 2009, nearly 87 percent higher than the $28.8 million, or $0.53 per unit, for the fourth quarter of 2008. For the year ended December 31, 2009, distributable cash flow available to limited partners was $311.4 million, or $5.66 per unit, compared to $288.7 million, or $5.44 per unit, for the same period in 2008.

Earnings before interest, taxes, depreciation and amortization (EBITDA) were $91.9 million for the fourth quarter of 2009 compared to $92.2 million for the fourth quarter of 2008. For the year ended December 31, 2009, EBITDA was $460.5 million compared to $491.6 million for the same period in 2008. Net income applicable to limited partners was $28.8 million, or $0.50 per unit, for the fourth quarter of 2009, compared to $25.2 million, or $0.46 per unit, earned in the fourth quarter of 2008. For the year ended December 31, 2009, net income applicable to limited partners was $191.7 million, or $3.47 per unit, compared to $224.2 million, or $4.22 per unit, for the same period in 2008.

“Fourth quarter 2009 distributable cash flow and net income were stronger compared to the same period last year primarily due to improvement in the asphalt and fuels marketing segment,” said Curt Anastasio, Chief Executive Officer and President of NuStar Energy L.P. and NuStar GP Holdings, LLC. “Results in this segment improved by $23.2 million in the fourth quarter of 2009 compared to last year primarily due to a higher margin per barrel in our asphalt operations. The margin per barrel in the fourth quarter of 2009 was $5.34 compared to $(1.66) last year. Since the fourth quarter 2008 results include a $22.7 million net gain resulting primarily from the sale of certain non-strategic pipeline and terminal assets, fourth quarter 2009 earnings were actually significantly higher than the fourth quarter of 2008.”

NuStar Energy L.P. also announced that its board of directors has declared a distribution of $1.065 per unit for the fourth quarter of 2009, which would equate to $4.26 per unit on an annual basis. This distribution will be paid on February 12, 2010, to holders of record as of February 5, 2010, and represents an increase over the $1.0575 per unit distribution for the fourth quarter of 2008. For 2009, NuStar Energy L.P. declared distributions of $4.245 per unit, which were nearly 4 percent higher than distributions of $4.085 per unit related to 2008.

-More-

“When you consider the challenging economic and market conditions experienced during the past year, I am especially proud of what we accomplished,” said Anastasio. “While many MLPs suspended their distribution, reduced it, or just maintained the distribution at current levels, NuStar Energy L.P. provided its investors a nearly four percent distribution increase and still maintained a solid distribution coverage ratio of 1.33 times. This was mainly due to the performance of our fee-based storage and transportation business segments, which demonstrated relative stability during the year despite weak refined product demand in 2009. Combined, our transportation and storage businesses generated an incremental $39 million of segmental EBITDA in 2009 compared to 2008. A strong tariff increase of 7.6 percent effective July 1, 2009 on our interstate pipelines, higher renewal rates at certain of our storage terminals and the completion of storage expansion projects under our previous $400 million construction program all contributed to higher results in these two segments.

“Our asphalt and fuels marketing business generated $80 million of segmental EBITDA in 2009, of which $70 million came from our asphalt operations. While our 2009 asphalt results were lower than what we originally anticipated, primarily due to weaker than expected demand, I am pleased with the cumulative performance of the operations. The adjusted EBITDA contribution for the nearly two years we’ve owned the asphalt operations, excluding the 2008 crude oil hedging loss, is now over $220 million, which is in line with our original acquisition economics. In addition, our thesis on growing tightness in supply continues to prove out as margins have already responded to favorable market fundamentals well before the full impact of coker capacity expansions in 2011 and 2012. The adjusted margin per barrel for 2008 and 2009, excluding the crude oil hedging loss incurred in 2008, averaged $7.55, which is significantly higher than what the estimated average margin per barrel was for the first seven years of the decade prior to NuStar’s acquisition.

“Our fee-based transportation and storage segments should continue to be relatively stable in 2010 as we expect to primarily benefit from projects started last year and higher renewal rates. To the extent the economy recovers, we expect this will also positively impact these segments. We do not expect to see as much incremental contribution in 2010 compared to 2009 since we reduced our 2009 growth capital in response to the financial crisis. However, we have significantly increased our internal growth program in 2010 to over $310 million, most of which are long-term contracts with guaranteed rates of return, and we should start to the see the benefit from these later in 2010 and more so in 2011.

“With the 2009 asphalt season over, our focus has now turned to the upcoming 2010 season, which should start up in April. We remain optimistic that we will see improved results in our asphalt operations in 2010 compared to 2009 as we expect a higher margin per barrel and

-More-

increased sales volumes. Even though year-over-year demand was down in 2009, the latest supply fundamentals through November 2009 show U.S. asphalt inventories continuing to decline well below the five-year average. This is mainly due to a larger decline in asphalt production, which has been impacted by low refinery utilization rates as a result of weak refining economics. We expect asphalt demand to be slightly higher in 2010 mainly due to increased stimulus spending and an improving economy. Higher demand and continued tightness in supply should result in improved margins. In addition, the U.S. refinery coker projects we are tracking, which are expected to further tighten asphalt supply as they come on line, are proceeding as planned. One of the coker projects expected to start up in the first quarter of 2010 has commenced operations.

“For the first quarter of 2010, we expect EBITDA to be similar to the fourth quarter and in the range of $80 to $100 million. This is reflective of the typical seasonal pattern in the asphalt operations as sales volumes and margins taper off and we start building inventories for the upcoming season. Business should start to pick up in the second quarter of 2010 as sales volumes and margins increase in response to warmer weather at the beginning of the asphalt season,” said Anastasio.

A conference call with management is scheduled for 11:00 a.m. ET (10:00 a.m. CT) today, January 29, 2010, to discuss the financial and operational results for the fourth quarter and full year 2009. Investors interested in listening to the presentation may call 800/622-7620, passcode 49455765. International callers may access the presentation by dialing 706/645-0327, passcode 49455765. The company intends to have a playback available following the presentation, which may be accessed by calling 800/642-1687, passcode 49455765. 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 crude oil and refined product pipelines; 82 terminal facilities that store and distribute crude oil, refined products and specialty liquids; four crude oil storage tank facilities; and two asphalt refineries with a combined throughput capacity of 104,000 barrels per day. The partnership’s combined system has over 91 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.

-More-

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 2008 annual report on Form 10-K and subsequent filings with the Securities and Exchange Commission. All information in this release is as of the date hereof, and we undertake no duty to update any forward-looking statement to conform the statement to actual results or changes in the partnership’s operations.

-30-

NuStar Energy L.P. and Subsidiaries

Consolidated Financial Information

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

	Three Months Ended December 31,						Year Ended December 31,
	2009			2008			2009			2008
Statement of Income Data:
Revenues:
Services revenues	$	196,216		$	192,855		$	745,349		$	740,630
Product sales		786,562			840,335			3,110,522			4,088,140
Total revenues		982,778			1,033,190			3,855,871			4,828,770
Costs and expenses:
Cost of product sales		744,663			828,233			2,883,187			3,864,310
Operating expenses		126,875			119,775			458,892			442,248
General and administrative expenses		27,204			20,445			94,733			76,430
Depreciation and amortization expense		37,420			35,690			145,743			135,709
Total costs and expenses		936,162			1,004,143			3,582,555			4,518,697
Operating income		46,616			29,047			273,316			310,073
Equity earnings from joint ventures		1,917			1,958			9,615			8,030
Interest expense, net		(18,858	)		(23,791	)		(79,384	)		(90,818	)
Other income, net		5,976			25,503			31,859			37,739
Income before income tax expense		35,651			32,717			235,406			265,024
Income tax (benefit) expense		(1,694	)		(65	)		10,531			11,006
Net income	$	37,345		$	32,782		$	224,875		$	254,018
Net income applicable to limited partners	$	28,800		$	25,196		$	191,665		$	224,171
Net income per unit applicable to limited partners (Note 1):	$	0.50		$	0.46		$	3.47		$	4.22
Weighted average number of basic units outstanding		57,523,049			54,460,549			55,232,467			53,182,741
EBITDA (Note 2)	$	91,929		$	92,198		$	460,533		$	491,551
Distributable cash flow (Note 2)	$	66,218		$	37,072		$	345,510		$	319,079
	December 31, 2009			December 31, 2008
Balance Sheet Data:
Debt, including current portion (a)	$	1,849,763		$	1,894,848
Partners’ equity (b)		2,484,968			2,206,997
Debt-to-capitalization ratio (a) / ((a)+(b))		42.7	%		46.2	%

NuStar Energy L.P. and Subsidiaries

Consolidated Financial Information - Continued

(Unaudited, Thousands of Dollars, Except Barrel Data)

	Three Months Ended December 31,						Year Ended December 31,
	2009			2008			2009			2008
Segment Data:
Storage:
Throughput (barrels/day)		667,655			701,736			667,169			742,599
Throughput revenues	$	18,705		$	22,128		$	78,353		$	90,918
Storage lease revenues		108,519			95,407			409,219			363,171
Total revenues		127,224			117,535			487,572			454,089
Operating expenses		68,645			62,486			245,439			246,304
Depreciation and amortization expense		18,416			17,158			70,888			66,706
Segment operating income	$	40,163		$	37,891		$	171,245		$	141,079
Transportation:
Refined products pipelines throughput (barrels/day)		566,694			648,295			573,778			673,687
Crude oil pipelines throughput (barrels/day)		357,392			352,897			351,888			392,110
Total throughput (barrels/day)		924,086			1,001,192			925,666			1,065,797
Revenues	$	80,919		$	83,808		$	302,070		$	317,778
Operating expenses		28,817			32,070			111,673			131,943
Depreciation and amortization expense		12,627			12,688			50,528			50,749
Segment operating income	$	39,475		$	39,050		$	139,869		$	135,086
Asphalt and fuels marketing: (Note 3)
Product sales	$	786,562		$	840,335		$	3,110,522		$	4,088,169
Cost of product sales		749,007			834,041			2,899,457			3,880,796
Operating expenses		37,297			29,285			130,973			80,133
Depreciation and amortization expense		4,927			4,862			19,463			14,734
Segment operating income	$	(4,669	)	$	(27,853	)	$	60,629		$	112,506
Consolidation and intersegment eliminations:
Revenues	$	(11,927	)	$	(8,488	)	$	(44,293	)	$	(31,266	)
Cost of product sales		(4,344	)		(5,808	)		(16,270	)		(16,486	)
Operating expenses		(7,884	)		(4,066	)		(29,193	)		(16,132	)
Total	$	301		$	1,386		$	1,170		$	1,352
Consolidated Information:
Revenues	$	982,778		$	1,033,190		$	3,855,871		$	4,828,770
Cost of product sales		744,663			828,233			2,883,187			3,864,310
Operating expenses		126,875			119,775			458,892			442,248
Depreciation and amortization expense		35,970			34,708			140,879			132,189
Segment operating income		75,270			50,474			372,913			390,023
General and administrative expenses		27,204			20,445			94,733			76,430
Other depreciation and amortization expense		1,450			982			4,864			3,520
Consolidated operating income	$	46,616		$	29,047		$	273,316		$	310,073

NuStar Energy L.P. and Subsidiaries

Consolidated Financial Information - Continued

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

Notes:

1. In 2008, the FASB provided additional guidance regarding the application of the two-class method to calculate earnings per unit for master limited partnerships, which was effective January 1, 2009. As a result, net income per unit applicable to limited partners for the three months ended December 31, 2008 changed from $0.47 previously reported.

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 December 31,						Year Ended December 31,
	2009			2008			2009			2008
Net income	$	37,345		$	32,782		$	224,875		$	254,018
Plus interest expense, net		18,858			23,791			79,384			90,818
Plus income tax expense		(1,694	)		(65	)		10,531			11,006
Plus depreciation and amortization expense		37,420			35,690			145,743			135,709
EBITDA		91,929			92,198			460,533			491,551
Less equity earnings from joint ventures		(1,917	)		(1,958	)		(9,615	)		(8,030	)
Less interest expense, net		(18,858	)		(23,791	)		(79,384	)		(90,818	)
Less reliability capital expenditures (a)		(12,248	)		(27,668	)		(45,163	)		(55,669	)
Income tax benefit (expense)		1,694			65			(10,531	)		(11,006	)
Plus distributions from joint ventures		2,950			2,335			9,700			2,835
Mark-to-market impact on hedge transactions (b)		2,668			(4,109	)		19,970			(9,784	)
Distributable cash flow		66,218			37,072			345,510			319,079
General partner’s interest in distributable cash flow		(9,266	)		(8,247	)		(34,142	)		(30,352	)
Limited partners’ interest in distributable cash flow	$	56,952		$	28,825		$	311,368		$	288,727
Distributable cash flow per limited partner unit	$	0.99		$	0.53		$	5.66		$	5.44

(a) For the fourth quarter and full year 2009, reliability capital expenditures were reduced by $14.1 million. The reduction consists of certain discretionary expenditures that do not relate to maintaining our equipment. Prospectively, we will not include these expenditures within reliability capital.

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

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