NuStar Energy (NS) 8-K NuStar Energy L.P. First Quarter 2011 Distributable Cash Flows

Exhibit 99.1

NuStar Energy L.P. First Quarter 2011 Distributable Cash Flows

Increase 98%

First Quarter 2011 Results Higher than First Quarter 2010 in all

Three Business Segments

Internal Growth Projects and Recent Acquisition Expected to Lead to Increased

Distributions and Improved Results in 2011

SAN ANTONIO, April 27, 2011 – NuStar Energy L.P. (NYSE: NS) today announced first quarter distributable cash flow available to limited partners of $45.1 million, or $0.70 per unit, compared to 2010 first quarter distributable cash flow of $22.8 million, or $0.38 per unit. First quarter earnings before interest, taxes, depreciation and amortization (EBITDA) were $92.8 million compared to first quarter 2010 EBITDA of $81.0 million.

NuStar Energy L.P. reported first quarter net income applicable to limited partners of $19.4 million, or $0.30 per unit, compared to $11.5 million, or $0.19 per unit, earned in the first quarter of 2010. The first quarter 2011 results include $5.0 million, or $0.08 per unit, of expenses related to the early termination of a 3^rd party storage agreement at NuStar’s Paulsboro, New Jersey asphalt refinery. Excluding the effect of these early termination costs and other items, first quarter 2011 adjusted net income applicable to limited partners would have been $26.1 million, or $0.40 per unit, which was higher than the first quarter street consensus of $0.33 per unit.

The partnership also announced that its board of directors has declared a first quarter 2011 distribution of $1.075 per unit. The first quarter 2011 distribution will be paid on May 13, 2011, to holders of record as of May 9, 2011 and is higher than the $1.065 per unit distribution paid in the first quarter of 2010. Distributable cash flow available to limited partners covers the distribution to the limited partners by 0.65 times for the first quarter of 2011.

“All three of our business segments generated higher operating income and EBITDA in the first quarter of 2011 when compared to the first quarter of 2010,” said Curt Anastasio, Chief Executive Officer and President of NuStar Energy L.P. and NuStar GP Holdings, LLC. “Increased shipments on higher tariff pipelines and operating expense efficiencies contributed to improved transportation segment results. Storage segment results benefited from the 2010 completion of several internal growth projects, most significantly our St. Eustatius terminal reconfiguration, as well as the May 2010 Mobile County, Alabama storage terminal acquisition.”

-More-

Anastasio added, “Improved results in our crude oil trading and products trading businesses contributed to higher first quarter 2011 results in the asphalt and fuels marketing segment. The decision to terminate the 3^rd party storage agreement was an important part of the favorable economics associated with our purchase of Pergrino crude oil for NuStar’s Paulsboro refinery, an accretive project that will start up at the end of 2011. The buy-out associated with the early termination of the storage agreement enabled us to avoid the capital expenditure required to build a new tank.”

Recent Internal Growth and Acquisition Activity

“NuStar and TexStar Midstream Services, LP recently announced that they have signed a letter of intent to develop a new pipeline system to transport Eagle Ford Shale crude and condensate to Corpus Christi. The pipeline throughput agreements and storage agreements associated with this new pipeline system should improve earnings in both our transportation and storage segments beginning in the second quarter of 2012,” said Anastasio.

Anastasio also noted, “Our acquisition of certain refining assets of the former AGE Refining is great news for our investors. We acquired these assets for $41 million and closed on the purchase on April 19, 2011. The refinery acquisition price represents about 20 percent of replacement cost and is expected to be immediately accretive to our earnings and cash flows. We have already hedged approximately 70 percent of the refinery’s production through the futures market for crude, distillates and gasoline-related products for the next three to four years. And by hedging a significant portion of the margins we expect this acquisition to pay out in approximately two years and realize a 70 percent rate of return.

Full-Year 2011 Outlook

Commenting on the full-year outlook for NuStar Energy L.P., Anastasio said, “We expect 2011 EBITDA and distributable cash flow results to be higher than 2010. These improved results should allow us to recommend a distribution increase to our Board of Directors again in 2011.”

Addressing business segment results Anastasio commented, “We expect EBITDA in our storage segment to be $25 to $35 million higher than 2010. This segment should benefit from internal growth projects completed in 2010 and 2011 as well as the Mobile County, Alabama terminal acquisition completed in May 2010 and the Turkey terminal acquisition completed in February 2011. EBITDA in our transportation segment should be $5 to $10 million lower due to reduced throughputs caused by the refinery turnaround activity of our customers and changing market conditions.”

-More-

In regard to the margin-based asphalt and fuels marketing segment, Anastasio added, “Earnings from the recently announced acquisition of some key AGE Refining assets, slightly improving asphalt margins and improved earnings in our fuels marketing operations should cause EBITDA in this segment to be $35 to $45 million higher than the $111 million of EBITDA earned in 2010.”

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

NuStar Energy L.P. is a publicly traded, limited partnership based in San Antonio, with 8,417 miles of pipeline; 90 terminal and storage facilities that store and distribute crude oil, refined products and specialty liquids; and two asphalt refineries and a fuels refinery with a combined throughput capacity of 118,500 barrels per day. The partnership’s combined system has over 94 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, Canada, Mexico, the Netherlands, the United Kingdom and Turkey. 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

-More-

to various risks, uncertainties and assumptions. These risks, uncertainties and assumptions are discussed in NuStar Energy L.P. and NuStar GP Holdings, LLC’s 2010 annual reports on Form 10-K and subsequent filings with the Securities and Exchange Commission.

-30-

-More-

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,
	2011			2010
Statement of Income Data:
Revenues:
Service revenues	$	198,393		$	189,295
Product sales		1,036,223			756,234
Total revenues		1,234,616			945,529
Costs and expenses:
Cost of product sales		992,367			719,221
Operating expenses		120,239			121,337
General and administrative expenses		25,983			27,269
Depreciation and amortization expense		40,296			37,929
Total costs and expenses		1,178,885			905,756
Operating income		55,731			39,773
Equity in earnings of joint venture		2,388			3,015
Interest expense, net		(20,457	)		(18,586	)
Other (expense) income, net		(5,499	)		301
Income before income tax expense		32,163			24,503
Income tax expense		3,647			4,800
Net income		28,516			19,703
Less net income attributable to noncontrolling interest		14			—
Net income applicable to NuStar Energy L.P.	$	28,502		$	19,703
Net income applicable to limited partners	$	19,365		$	11,511
Net income per unit applicable to limited partners	$	0.30		$	0.19
Weighted average limited partner units outstanding		64,610,549			60,210,549
EBITDA attributable to NuStar Energy L.P. (Note 1)	$	92,794		$	81,018
Distributable cash flow attributable to NuStar Energy L.P. (Note 1)	$	55,268		$	32,049
	March 31, 2011			December 31, 2010
Balance Sheet Data:
Debt, including current portion (a)	$	2,362,296		$	2,137,080
Partners’ equity (b)		2,678,583			2,702,700
Debt-to-capitalization ratio (a) / ((a)+(b))		46.9	%		44.2	%

NuStar Energy L.P. and Subsidiaries

Consolidated Financial Information - Continued

(Unaudited, Thousands of Dollars, Except Barrel Data)

	Three Months Ended March 31,
	2011			2010
Segment Data:
Storage:
Throughput (barrels/day)		620,582			641,457
Throughput revenues	$	17,048		$	17,827
Storage lease revenues		119,727			108,805
Total revenues		136,775			126,632
Operating expenses		66,949			65,078
Depreciation and amortization expense		21,130			18,666
Segment operating income	$	48,696		$	42,888
Transportation:
Refined products pipelines throughput (barrels/day)		502,610			527,340
Crude oil pipelines throughput (barrels/day)		310,865			363,237
Total throughput (barrels/day)		813,475			890,577
Revenues	$	73,010		$	75,262
Operating expenses		25,906			28,753
Depreciation and amortization expense		12,707			12,752
Segment operating income	$	34,397		$	33,757
Asphalt and fuels marketing:
Product sales	$	1,040,068		$	758,930
Cost of product sales		1,001,073			726,734
Gross margin		38,995			32,196
Operating expenses		33,980			35,051
Depreciation and amortization expense		4,897			5,041
Segment operating income (loss)	$	118		$	(7,896	)
Consolidation and intersegment eliminations:
Revenues	$	(15,237	)	$	(15,295	)
Cost of product sales		(8,706	)		(7,513	)
Operating expenses		(6,596	)		(7,545	)
Total	$	65		$	(237	)
Consolidated Information:
Revenues	$	1,234,616		$	945,529
Cost of product sales		992,367			719,221
Operating expenses		120,239			121,337
Depreciation and amortization expense		38,734			36,459
Segment operating income		83,276			68,512
General and administrative expenses		25,983			27,269
Other depreciation and amortization expense		1,562			1,470
Consolidated operating income	$	55,731		$	39,773

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,
	2011			2010
Net income	$	28,516		$	19,703
Plus interest expense, net		20,457			18,586
Plus income tax expense		3,647			4,800
Plus depreciation and amortization expense		40,296			37,929
EBITDA		92,916			81,018
Less equity earnings from joint ventures		(2,388	)		(3,015	)
Less interest expense, net		(20,457	)		(18,586	)
Less reliability capital expenditures		(8,008	)		(12,355	)
Less income tax expense		(3,647	)		(4,800	)
Plus distributions from joint venture		2,923			2,400
Mark-to-market impact on hedge transactions (a)		(5,960	)		(12,613	)
Distributable cash flow	$	55,379		$	32,049
EBITDA	$	92,916		$	81,018
EBITDA attributable to noncontrolling interest		122			—
EBITDA attributable to NuStar Energy L.P.	$	92,794		$	81,018
Distributable cash flow	$	55,379		$	32,049
Distributable cash flow attributable to noncontrolling interest		111			—
Distributable cash flow attributable to NuStar Energy L.P.	$	55,268		$	32,049
General partner’s interest in distributable cash flow		(10,160	)		(9,266	)
Limited partners’ interest in distributable cash flow	$	45,108		$	22,783
Distributable cash flow per limited partner unit	$	0.698		$	0.378

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