Exhibit 99.1

NuStar Energy Reports Earnings Results for Second Quarter of 2012

Non-cash Charges and Loss in Asphalt and Fuels Marketing Segment

Negatively Affect Results but Quarterly Distribution Stands at $1.095

Storage and Transportation Segment Second Quarter and

Year to Date Results Higher than Last Year

Expect to Close Asphalt Joint Venture Transaction in the Third Quarter

SAN ANTONIO, July 27, 2012 — NuStar Energy L.P. (NYSE: NS) today announced second quarter distributable cash flow available to limited partners of $16.9 million, or $0.24 per unit, compared to 2011 second quarter distributable cash flow of $119.4 million, or $1.85 per unit.  Second quarter earnings before interest, taxes, depreciation and amortization (EBITDA) was negative $161.2 million compared to second quarter 2011 EBITDA of $160.0 million.

The company reported a second quarter net loss applicable to limited partners of $251.6 million, or $3.56 per unit, compared to net income applicable to limited partners of $81.8 million, or $1.27 per unit, earned in the second quarter of 2011.  Without certain adjustments in the second quarters of both years, as described below, the second quarter of 2012 would have generated adjusted net income applicable to limited partners of $4.4 million, or $0.06 per unit, compared to the second quarter 2011 adjusted net income applicable to limited partners of $86.4 million, or $1.34 per unit.

For the six months ended June 30, 2012, the company reported a net loss applicable to limited partners of $235.6 million, or $3.33 per unit, compared to net income applicable to limited partners of $101.1 million, or $1.57 per unit, for the six months ended June 30, 2011.

The partnership also announced that its board of directors has declared a second quarter 2012 distribution of $1.095 per unit.  The second quarter 2012 distribution will be paid on August 10, 2012, to holders of record as of August 7, 2012.  Distributable cash flow available to limited partners covers the distribution to the limited partners by 0.22 times for the second quarter of 2012.

-More-

“We have several transactions and internal growth projects in the works that we’re confident will improve our earnings going forward,” said Curt Anastasio, Chief Executive Officer and President of NuStar Energy L.P. and NuStar GP Holdings, LLC. “We remain committed to growing our distributions to our unitholders, so we have been very focused on minimizing our earnings volatility and reducing our debt in order to invest in more stable, high-return pipeline and terminal projects.”

Anastasio went on to say, “The asphalt joint venture that we are forming with Lindsay Goldberg is expected to deconsolidate our asphalt operations, while allowing us to maintain a 50% interest in a business that has the potential to generate significant cash flows as the U.S. economy improves.  The closing for the transaction is still expected to be completed by September 30, 2012.  As a result of this transaction NuStar expects to reduce its debt levels by $400 to $500 million subject to the joint venture’s working capital requirements.

“We also have completed several high-return growth projects in our storage and transportation segments, and we have many more in various stages of development that are expected to contribute significantly to our earnings going forward.  All of these initiatives should position the company well for the coming years.”

Second Quarter Adjustments

The second quarter 2012 results included $271.8 million, or $3.77 per unit, of non-cash expenses related to asset impairments.  These asset impairment charges relate primarily to a write down of PP&E, Goodwill and other intangible assets associated with the company’s asphalt operations. This charge is a result of the expected sale of 50% of these operations to an affiliate of Lindsay Goldberg LLC.  As noted above, excluding these items and other adjustments, second quarter 2012 adjusted net income applicable to limited partners would have been $4.4 million, or $0.06 per unit.

The second quarter 2011 results included $4.0 million, or $0.06 per unit, net of tax, of expenses related primarily to the write-off of project costs associated with certain capital projects cancelled during the quarter.  As noted above, excluding this item and other adjustments, second quarter 2011 adjusted net income applicable to limited partners would have been $86.4 million, or $1.34 per unit

-More-

Segment Results

“Our storage and transportation segments continue to benefit from several internal growth projects completed in 2011 and the first half of 2012,” said Anastasio.  “As a result, EBITDA in both our storage and transportation segments were higher than last year’s second quarter and last year’s six month period ending June 30th.  Our storage segment benefited primarily from the third quarter 2011 completion of a storage expansion project and the April 2012 completion of a unit train offloading facility project, both at our St. James, Louisiana terminal facility. Higher pipeline tariffs as well as increased throughputs and new revenue streams from two Eagle Ford Shale region internal growth projects completed in the last half of 2011 contributed to improved results in our transportation segment.”

Anastasio added, “In our Asphalt and Fuels Marketing segment, continued weak demand,  low gross margins and the non-cash asset impairment charge caused the results for our asphalt operations to be negative in the second quarter and significantly lower than the results for last year’s six-month period ending June 30th.  In addition, the company’s fuels marketing operations generated a loss in the quarter primarily as a result of heavy fuel oil and bunker fuel inventories not being hedged.”

Earnings Outlook for the Remainder of 2012

In the last half of 2012, the company expects to benefit from the July 1, 2012 FERC tariff adjustment, the completion of two new pipeline projects in the Eagle Ford Shale region and the completion of a one million barrel expansion project at the St. Eustatius terminal facility.  These projects should contribute to higher EBITDA in the last half of 2012 when compared to the last half of 2011.

“We just completed another pipeline project in the Eagle Ford Shale region the first week of July.  This was the third pipeline project we have completed in the Eagle Ford in the past year.  We expect to complete another project in the region by the end of the third quarter and expect to announce more Eagle Ford projects before the end of the year,” said Anastasio.

In regard to the full-year outlook for NuStar Energy L.P.’s business segments Anastasio commented, “We expect EBITDA in both our storage and transportation segments to be higher than last year.  Storage segment EBITDA is expected to be $25 to $35 million higher than 2011 while EBITDA in our transportation segment should be $10 to $20 million higher than last year.”

-More-

Anastasio then stated, “Lower earnings in our asphalt operations as well as our fuels marketing operations should cause EBITDA in our asphalt and fuels marketing segment to be significantly lower than last year.”

A conference call with management is scheduled for 10:00 a.m. ET (9:00 a.m. CT) today, July 27, 2012, to discuss the financial and operational results for the second quarter of 2012.  Investors interested in listening to the presentation may call 800/622-7620, passcode 95963671.  International callers may access the presentation by dialing 706/645-0327, passcode 95963671.  The company intends to have a playback available following the presentation, which may be accessed by calling 800/585-8367, passcode 95963671.  International callers may access the playback by calling 404/537-3406, reservation passcode 95963671.  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,433 miles of pipeline; 84 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 approximately 96 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, including St. Eustatius in the Caribbean, 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.

-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 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 2011 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)

NuStar Energy L.P. and Subsidiaries

Consolidated Financial Information - Continued

(Unaudited, Thousands of Dollars, Except Barrel Data)

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:

(a)    Other non-cash items for the three and six months ended June 30, 2012 primarily consist of long-lived asset impairment charges related to our asphalt operations, including fixed assets, goodwill and intangible assets.  These impairment charges were partially offset by a gain resulting from a legal settlement.

(b)    Distributable cash flow excludes the impact of unrealized mark-to-market gains and losses that arise from valuing certain derivative contracts, as well as the associated hedged inventory.  The gain or loss associated with these contracts is realized in distributable cash flow when the contracts are settled.