Exhibit 99.1

NuStar CFO Steve Blank to Retire at Year-End; Tom Shoaf Selected as Successor

Jorge Del Alamo Named Controller

Amy Perry & Karen Thompson Promoted to General Counsel

December 20, 2013 03:24 PM Eastern Standard Time

SAN ANTONIO—(BUSINESS WIRE)—NuStar Energy L.P. (NYSE: NS) announced today that Steve Blank, Executive Vice President and CFO of NuStar Energy L.P. and NuStar GP Holdings, plans to retire from the company effective December 31, 2013. The company’s board of directors has selected Tom Shoaf, NuStar’s Controller, to serve as Executive Vice President and Chief Financial Officer upon Blank’s retirement, and Jorge Del Alamo, NuStar’s Assistant Controller, has been promoted to Vice President and Controller.

The company also announced that Amy Perry and Karen Thompson, both of whom serve as Vice President and Assistant General Counsel at NuStar, will succeed Brad Barron, Executive Vice President and General Counsel, when he becomes President and CEO on January 1, 2014. Perry is being promoted to Senior Vice President, Corporate Secretary and General Counsel — Corporate & Commercial Law, and Thompson is being promoted to Senior Vice President and General Counsel — Litigation, Regulatory & Environmental.

Blank to Retire & Shoaf to Succeed Him as CFO

“Throughout his long career with the company, Steve has made countless contributions to our success and has built a top-notch Accounting/Finance organization from the ground up,” said Curt Anastasio, NuStar’s President and CEO. “His fiscal responsibility, strong principles and personal integrity have contributed to NuStar’s reputation as one of the most trustworthy companies in corporate America. Also since our inception, Steve’s extensive knowledge of the financial industry has been an important component of our strategic planning effort.”

Barron praised Blank for contributing to NuStar’s growth and building one of the best finance departments in the industry. “Steve contributed to NuStar’s tremendous growth over the years as he was a key player in every major transaction from the time of the formation of our company through today. Thanks to Steve, we’re fortunate to have an outstanding Finance Department with a great group of employees and many strong leaders who have numerous years of experience, a thorough understanding of our business, and a commitment to NuStar’s guiding principles.

“When we contemplated a successor for Steve, we knew that we wanted someone who could work collaboratively with the other executives in Finance, as well as in other departments at the corporate office and in our field operations. And without a doubt, Tom has the leadership skills, experience and personality to do just that. We have no doubt that he will do a great job of leading this organization as he has nearly 30 years of experience in his field, solid leadership skills, the highest ethical standards, a strong work ethic and great interpersonal skills,” said Barron.

Prior to becoming NuStar’s Controller eight years ago, Shoaf served in positions of increasing responsibility with Valero Energy Corporation, eventually becoming Director of Finance. Shoaf started his career as an Accountant with City Public Service, San Antonio’s energy utility company, after graduating with a bachelor of business administration degree in accounting from Abilene Christian University. In recognition of his experience and achievements over the years, Shoaf was named the Top Controller by the San Antonio Business Journal in 2012.

Del Alamo Selected as Controller

“Tom has chosen an outstanding accounting executive and strong leader to succeed him,” said Barron. “Jorge has done a great job in his current position, as he has the unique ability to focus on the details without losing sight of the big picture. He has helped ensure that our financial statements reflect the most accurate and up-to-date disclosure, our budgets and forecasts are as precise as possible, and our capital expenses are properly planned and allocated.”

Del Alamo joined Valero in 2003 as Director of Sarbanes Oxley, and subsequently moved over to NuStar as Director of Financial Reporting. Prior to that, he served as the Controller of Fuego, Inc., as CFO and Controller of Life Systems, Inc., and as a Sr. Manager of Ernst & Young LLP.

Perry & Thompson Appointed General Counsel

“Our Legal Department has a very strong leadership team and an outstanding group of professionals who are incredibly smart, hard-working, dedicated and accomplished,” said Barron. “And Amy Perry and Karen Thompson have done an outstanding job of handling many complex legal issues, ranging from overseeing complicated acquisitions to successfully resolving challenging legal disputes. So I am looking forward to expanding their roles within the company and having their involvement on the senior leadership team.”

Since joining the company nearly 11 years ago, Perry has overseen its corporate finance and commercial transactions, corporate governance, external legal reporting, and employee benefits issues. Prior to NuStar, she served as Counsel — Corporate Law for Valero, and prior to that she practiced corporate, mergers & acquisitions and securities law at DLA Piper in New York City and Wilson Sonsini Goodrich & Rosati in Austin. In her new role, she will continue to be responsible for the same areas within the company’s Legal Department and will continue to serve as Corporate Secretary, but she also will oversee the Ad Valorem Tax and Right-of-Way departments.

Thompson joined the company approximately 12 years ago, and since that time she has resolved many complex issues, providing legal advice and support regarding litigation, disputes, environmental and regulatory matters. Prior to joining the company, she served as Managing Counsel for Valero and practiced law at Mayor, Day, Caldwell &

Keeton in Houston. Thompson will continue to be responsible for all litigation and regulatory issues, plus she will now oversee Risk Management, Health, Safety & Environmental, and Customs & Trade.

About NuStar Energy L.P.

NuStar Energy L.P., a publicly traded master limited partnership based in San Antonio, is one of the largest independent liquids terminal and pipeline operators in the nation. NuStar currently has 8,643 miles of pipeline; 87 terminal and storage facilities that store and distribute crude oil, refined products and specialty liquids; and 50% ownership in a joint venture that owns a terminal and an asphalt refinery with a throughput capacity of 74,000 barrels per day. The partnership’s combined system has approximately 97 million barrels of storage capacity, and 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.

Contacts

NuStar Energy L.P.

Media:

Mary Rose Brown, 210-918-2314

maryrose.brown@nustarenergy.com

Investors:

Chris Russell, 210-918-3507

chris.russell@nustarenergy.com