Exhibit 1.1

EXECUTION COPY

$350,000,000

NUSTAR LOGISTICS, L.P.

7.65% Senior Notes due 2018

guaranteed by

NuStar Energy L.P. and NuStar Pipeline Operating Partnership L.P.

UNDERWRITING AGREEMENT

April 1, 2008

BARCLAYS CAPITAL INC.

J.P. MORGAN SECURITIES INC.

SUNTRUST ROBINSON HUMPHREY, INC.

As Representatives of the several

Underwriters named in Schedule I attached hereto,

c/o Barclays Capital Inc.

200 Park Avenue

New York, New York 10166

and

J.P. Morgan Securities Inc.

270 Park Avenue

New York, New York 10017

Ladies and Gentlemen:

NuStar Logistics, L.P., a Delaware limited partnership (“ NuStar Logistics ”), proposes to issue and sell $350,000,000 aggregate principal amount of its 7.65% Senior Notes due 2018 (the “ Notes ”) to the underwriters (the “ Underwriters ”) named in Schedule I attached to this agreement (this “ Agreement ”), to be fully and unconditionally guaranteed on a senior, unsecured basis by NuStar Energy L.P., a Delaware limited partnership (the “ Partnership ”), and NuStar Pipeline Operating Partnership L.P., a Delaware limited partnership formerly known as Kaneb Pipe Line Operating Partnership, L.P. (“ NPOP ”) (the “ Guarantee ,” and together with the Notes, the “ Securities ”). The Securities are to be issued under the indenture dated as of July 15, 2002 (as amended and supplemented to date, the “ Base Indenture ”), among NuStar Logistics, as issuer, the Partnership and NPOP, as guarantors, and Wells Fargo Bank, National Association (as successor to The Bank of New York Trust Company, N.A.), as trustee (the “ Trustee ”), as supplemented by the Fourth Supplemental Indenture thereto to be dated as of the Delivery Date (as defined in Section 3 hereof) (the “ Supplemental Indenture ” and, together with the Base Indenture, the “ Indenture ”).

This is to confirm the agreement among the Partnership, Riverwalk Logistics, L.P., a Delaware limited partnership and the general partner of the Partnership (the “ General

1

Partner ”), NuStar GP, LLC, a Delaware limited liability company and the general partner of the General Partner (“ NuStar GP ”), NuStar Logistics, NuStar GP, Inc., a Delaware corporation and the general partner of NuStar Logistics (“ GP, Inc. ”), NPOP and NuStar Pipeline Company, LLC, a Delaware limited liability company formerly known as Kaneb Pipe Line Company LLC and the general partner of NPOP (“ NuStar Pipeline GP ”), and the Underwriters concerning the purchase of the Notes from NuStar Logistics by the Underwriters. The Partnership, the General Partner, NuStar GP, NuStar Logistics, GP, Inc., NPOP and NuStar Pipeline GP are collectively referred to herein as the “ Partnership Parties .”

A. It is understood and agreed to by all parties hereto that NuStar GP Holdings, LLC, a Delaware limited liability company (“ NuStar Holdings ”), owns as of the Delivery Date (as defined in Section 3 hereof):

(i) a 2% general partner interest in the Partnership, held indirectly through a 100% indirect ownership interest in the General Partner;

(ii) 10,213,894 Common Units held indirectly through a 100% ownership interest in Riverwalk Holdings, LLC, a Delaware limited liability company (“ Riverwalk Holdings ”);

(iii) 6,416 Common Units held indirectly through a 100% ownership interest in NuStar GP; and

(iv) all of the incentive distribution rights in the Partnership (the “ Incentive Distribution Rights ”), held indirectly through a 100% ownership interest in the General Partner;

each as more particularly described in the Preliminary Prospectus and the Prospectus (as such terms are hereinafter defined).

B. It is further understood and agreed to by all parties hereto that as of the date hereof the Partnership owns:

(i) a 99.99% limited partner interest in NuStar Logistics;

(ii) a 0.01% general partner interest in NuStar Logistics, indirectly held through its 100% ownership interest in GP, Inc.;

(iii) a 99% limited partner interest in NuStar Pipeline Partners L.P., a Delaware limited partnership formerly known as Kaneb Pipe Line Partners, L.P. (“ NPP ”);

(iv) a 1% general partner interest in NPP, indirectly held through a 100% indirect ownership interest in NuStar Pipeline GP;

(v) a 100% membership interest in NuStar Pipeline GP and the general partner of NPP and NPOP, as hereinafter defined, held indirectly through a 100% membership interest in LegacyStar Services, LLC, a Delaware limited liability company formerly known as Kaneb Services, LLC and sole member of NuStar Pipeline GP (“ LegacyStar Services ”);

2

(vi) a 100% ownership interest in NPOP (together with NPP, NuStar Pipeline GP and LegacyStar Services, the “ NuStar OLP Entities ”), held indirectly through NPP and NuStar Pipeline GP; and

(vii) a 100% ownership interest in each of the subsidiaries listed on Schedule II hereto, except as otherwise indicated on Schedule II (collectively, the “ Operating Subsidiaries ” and each individually an “ Operating Subsidiary ”), held, directly or indirectly, through either of NuStar Logistics or NPOP.

NuStar GP, Riverwalk Holdings, the Partnership, the General Partner, NuStar Logistics, GP, Inc. and the NuStar OLP Entities are collectively referred to herein as the “ Partnership Entities .”

C. Prior to the execution hereof:

(i) CITGO Asphalt Refining Company, a New Jersey general partnership, and NuStar Asphalt Refining, LLC, a Delaware limited liability company and wholly owned subsidiary of the Partnership (“ NuStar Asphalt ”), entered into a Sale and Purchase Agreement dated November 5, 2007 (the “ CARCO Purchase Agreement ”);

(ii) NuStar Logistics, the Partnership and NPOP entered into a 5-Year Revolving Credit Agreement dated as of December 10, 2007 with JPMorgan Chase Bank, N.A., as Administrative Agent, SunTrust Bank, as Syndication Agent, Barclays Bank PLC and Mizuho Corporate Bank Ltd., as Co-Documentation Agents, and the Lenders party thereto; and

(iii) NuStar Logistics and the Partnership entered into a Term Loan Credit Agreement dated as of February 1, 2008 with JPMorgan Chase Bank, N.A., as Administrative Agent, SunTrust Bank, as Syndication Agent, Barclays Bank PLC and Wachovia Bank, National Association, as Co-Documentation Agents, and the Lenders party thereto.

D. It is further understood and agreed to by all parties hereto that the following additional transactions will occur substantially contemporaneously with the Delivery Date (as defined in Section 3 hereof):

(i) NuStar Logistics, the Partnership, NPOP and the Trustee shall have entered into the Supplemental Indenture to conform to the description thereof set forth in the Prospectus (as defined in Section 1).

The “ Organizational Documents ” shall mean the NuStar GP LLC Agreement, the Riverwalk Holdings LLC Agreement, the GP Partnership Agreement, the Partnership Agreement, the NuStar Logistics Partnership Agreement, the LegacyStar Services LLC Agreement, the NuStar Pipeline GP LLC Agreement, the NPP Partnership Agreement and the NPOP Partnership Agreement (as such terms are defined in Section 1 hereof).

3

The Partnership Parties wish to confirm as follows their agreement with you in connection with the purchase of the Notes from NuStar Logistics by the Underwriters.

1. Representations, Warranties and Agreements of the Partnership Parties. Each of the Partnership Parties represents, warrants and agrees that:

(a) Registration; Definitions; No Stop Order . A registration statement (Registration No. 333-143095) on Form S-3 relating to the Securities has (i) been prepared by the NuStar Logistics, the Partnership and NPOP in conformity with the requirements of the Securities Act of 1933, as amended (the “ Securities Act ”), and the rules and regulations (the “ Rules and Regulations ”) of the Securities and Exchange Commission (the “ Commission ”) promulgated thereunder; (ii) been filed with the Commission under the Securities Act; and (iii) become effective under the Securities Act. Copies of such registration statement and any amendment thereto have been delivered or otherwise made available by the Partnership to you as the representatives of the Underwriters (the “ Representatives ”). As used in this Agreement:

(i) “ Applicable Time ” means 6:00 p.m. (New York City time) on April 1, 2008;

(ii) “ Effective Date ” means any date as of which any part of such registration statement relating to the Securities became, or is deemed to have become, effective under the Securities Act in accordance with the Rules and Regulations;

(iii) “ Final Term Sheet ” means the term sheet prepared pursuant to Section 4(a) of the Agreement and substantially in the form attached in Schedule IV hereto;

(iv) “ Issuer Free Writing Prospectus ” means each “free writing prospectus” (as defined in Rule 405 of the Rules and Regulations) prepared by or on behalf of NuStar Logistics, the Partnership and NPOP or used or referred to by NuStar Logistics, the Partnership or NPOP in connection with the offering of the Securities, including the Final Term Sheet;

(v) “ Preliminary Prospectus ” means any preliminary prospectus relating to the Securities included in such registration statement or filed with the Commission pursuant to Rule 424(b) of the Rules and Regulations, including any preliminary prospectus supplement thereto relating to the Securities;

(vi) “ Pricing Disclosure Package ” means, as of the Applicable Time, the most recent Preliminary Prospectus, together with each Issuer Free Writing Prospectus set forth on Schedule III hereto;

4

(vii) “ Prospectus ” means the final prospectus relating to the Securities, including any prospectus supplement thereto relating to the Securities, as filed with the Commission pursuant to Rule 424(b) of the Rules and Regulations; and

(viii) “ Registration Statement ” means, collectively, the various parts of such registration statement, each as amended as of the Effective Date for such part, including any Preliminary Prospectus or the Prospectus and all exhibits to such registration statement.

Any reference to any Preliminary Prospectus or the Prospectus shall be deemed to refer to and include any documents incorporated by reference therein pursuant to Form S-3 under the Securities Act as of the date of such Preliminary Prospectus or the Prospectus, as the case may be. Any reference to the “ most recent Preliminary Prospectus ” shall be deemed to refer to the latest Preliminary Prospectus included in the Registration Statement or filed pursuant to Rule 424(b) on or prior to the date hereof. Any reference to any amendment or supplement to any Preliminary Prospectus or the Prospectus shall be deemed to refer to and include any document filed under the Securities Exchange Act of 1934, as amended (the “ Exchange Act ”), after the date of such Preliminary Prospectus or the Prospectus, as the case may be, and incorporated by reference in such Preliminary Prospectus or the Prospectus, as the case may be; and any reference to any amendment to the Registration Statement shall be deemed to include, for so long as the delivery of a prospectus is required in connection with the offering or sale of the Securities, any reports of the Partnership filed with the Commission pursuant to Sections 13(a), 13(c) or 15(d) of the Exchange Act after the Effective Date that is incorporated by reference in the Registration Statement. The Commission has not issued any order preventing or suspending the use of any Preliminary Prospectus or the Prospectus or suspending the effectiveness of the Registration Statement, and no proceeding or examination for such purpose has been instituted or threatened by the Commission. The Commission has not notified the Partnership of any objection to the use of the form of the Registration Statement.

(b) Partnership Status as “Well-Known Seasoned Issuer.” The Partnership has been since the time of initial filing of the Registration Statement and continues to be a “well-known seasoned issuer” (as defined in Rule 405) eligible to use Form S-3 for the offering of the Securities, including not having been an “ineligible issuer” (as defined in Rule 405) at any such time or date. The Registration Statement is an “automatic shelf registration statement” (as defined in Rule 405) and was filed not earlier than the date that is three years prior to the Delivery Date (as defined in Section 3 hereof).

(c) Registration Statement and Prospectus Conform to the Requirements of the Securities Act . The Registration Statement conformed when filed and, on the Effective Date and on the Delivery Date, will conform in all material respects, and any amendment to the Registration Statement filed after the date hereof will conform in all material respects when filed, to the requirements of the Securities Act and the Rules and Regulations. The Preliminary Prospectus conformed when filed, and the Prospectus will conform, in all material respects when filed with the Commission pursuant to Rule 424(b) and on the Delivery Date, to the requirements of the Securities Act and the Rules and Regulations. The documents incorporated by reference in any Preliminary Prospectus or the Prospectus conformed, and any further documents so incorporated will conform,

5

when filed with the Commission, in all material respects to the requirements of the Exchange Act or the Securities Act, as applicable, and the rules and regulations of the Commission thereunder.

(d) No Material Misstatements or Omissions in Registration Statement . The Registration Statement did not, as of the Effective Date, contain an untrue statement of a material fact or omit to state a material fact required to be stated therein or necessary to make the statements therein not misleading; provided that no representation or warranty is made as to information contained in or omitted from the Registration Statement in reliance upon and in conformity with written information furnished to the Partnership through the Representatives by or on behalf of any Underwriter specifically for inclusion therein, which information is specified in Section 7(e).

(e) No Material Misstatements or Omissions in Prospectus . The Prospectus will not, as of its date and on the Delivery Date, contain an untrue statement of a material fact or omit to state a material fact necessary to make the statements therein, in the light of the circumstances under which they were made, not misleading; provided that no representation or warranty is made as to information contained in or omitted from the Prospectus in reliance upon and in conformity with written information furnished to the Partnership through the Representatives by or on behalf of any Underwriter specifically for inclusion therein, which information is specified in Section 7(e).

(f) No Material Misstatements or Omissions in Documents Incorporated by Reference. The documents incorporated by reference in any Preliminary Prospectus or the Prospectus did not, and any further documents filed and incorporated by reference therein will not, when filed with the Commission, contain an untrue statement of a material fact or omit to state a material fact necessary to make the statements therein, in the light of the circumstances under which they were made, not misleading.

(g) No Material Misstatements or Omissions in Pricing Disclosure Package . The Pricing Disclosure Package did not, as of the Applicable Time, contain an untrue statement of a material fact or omit to state a material fact necessary to make the statements therein, in the light of the circumstances under which they were made, not misleading; provided that no representation or warranty is made as to information contained in or omitted from the Pricing Disclosure Package in reliance upon and in conformity with written information furnished to the Partnership through the Representatives by or on behalf of any Underwriter specifically for inclusion therein, which information is specified in Section 7(e).

(h) No Material Misstatements or Omissions in Issuer Free Writing Prospectuses . Each Issuer Free Writing Prospectus (including, without limitation, any road show that constitutes a free writing prospectus under Rule 433), when considered together with the Pricing Disclosure Package as of the Applicable Time, (i) did not contain an untrue statement of a material fact or omit to state a material fact required to be stated therein or necessary to make the statements therein, in the light of the circumstances under which they were made, not misleading and (ii) did not conflict with the information then contained in the Registration Statement.

6

(i) Issuer Free Writing Prospectuses Conform to the Requirements of the Securities Act . Each Issuer Free Writing Prospectus conformed or will conform in all material respects to the requirements of the Securities Act and the Rules and Regulations on the date of first use, and NuStar Logistics, the Partnership and NPOP have complied with all prospectus delivery requirements and any filing and record keeping requirements applicable to such Issuer Free Writing Prospectus pursuant to the Rules and Regulations. None of NuStar Logistics, the Partnership or NPOP has made any offer relating to the Securities that would constitute an Issuer Free Writing Prospectus without the prior consent of the Representatives. NuStar Logistics, the Partnership and NPOP have retained in accordance with the Rules and Regulations all Issuer Free Writing Prospectuses that were not required to be filed pursuant to the Rules and Regulations. Each of NuStar Logistics, the Partnership and NPOP has taken all actions necessary so that any “road show” (as defined in Rule 433 of the Rules and Regulations) in connection with the offering of the Securities will not be required to be filed pursuant to the Rules and Regulations.

(j) Formation and Qualification . Each of the Partnership Entities has been duly organized and is validly existing and in good standing as a limited partnership, limited liability company or corporation, as applicable, under the laws of its jurisdiction of organization and is duly qualified to do business and in good standing as a foreign limited partnership, foreign limited liability company or foreign corporation, as applicable, in each jurisdiction in which its ownership or lease of property or the conduct of its business requires such qualification, except where the failure to be so qualified or in good standing would not, and except where the failure of the Partnership Entities to be so duly organized would not, (i) in the aggregate, reasonably be expected to have a material adverse effect on the condition (financial or otherwise), results of operations, unitholders’ or stockholders’ equity, properties, business or prospects of the Partnership and its subsidiaries (as defined in Rule 405) taken as a whole (a “ Material Adverse Effect ”); or (ii) subject the partners of the Partnership to any material liability or disability; and each of the Partnership Entities has all power and authority necessary to own or hold its properties and to conduct the businesses in which it is engaged in all material respects as described in the Pricing Disclosure Package.

(k) Ownership of Riverwalk Holdings by NuStar Holdings. NuStar Holdings is the sole member of Riverwalk Holdings and owns 100% of the issued and outstanding membership interests in Riverwalk Holdings; such membership interests have been duly authorized and validly issued in accordance with the limited liability company agreement of Riverwalk Holdings (the “ Riverwalk Holdings LLC Agreement ”), and are fully paid (to the extent required under the Riverwalk Holdings LLC Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 18-607 of the Delaware Limited Liability Company Act (the “ Delaware LLC Act ”)); and NuStar Holdings owns such membership interests free and clear of all liens, encumbrances, security interests, charges or claims.

(l) Ownership of NuStar GP by NuStar Holdings. NuStar Holdings is the sole member of NuStar GP and owns 100% of the issued and outstanding membership interests in NuStar GP; such membership interests have been duly authorized and validly

7

issued in accordance with the limited liability company agreement of NuStar GP (the “ NuStar GP LLC Agreement ”), and are fully paid (to the extent required under the NuStar GP LLC Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 18-607 of the Delaware LLC Act); and NuStar Holdings owns such membership interests free and clear of all liens, encumbrances, security interests, charges or claims.

(m) Ownership of the General Partner Interest in the General Partner . NuStar GP is the sole general partner of the General Partner with a 0.1% general partner interest in the General Partner; such general partner interest has been duly authorized and validly issued in accordance with the limited partnership agreement of the General Partner (the “ GP Partnership Agreement ”); and NuStar GP owns such general partner interest free and clear of all liens, encumbrances, security interests, charges or claims.

(n) Ownership of the Limited Partner Interests in the General Partner . Riverwalk Holdings is the sole limited partner of the General Partner with a 99.9% limited partner interest in the General Partner; such limited partner interest has been duly authorized and validly issued in accordance with the GP Partnership Agreement and is fully paid (to the extent required under the GP Partnership Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 17-607 of the Delaware LP Revised Uniform Limited Partnership Act (the “ Delaware LP Act ”)); and Riverwalk Holdings owns such limited partner interest free and clear of all liens, encumbrances, security interests, charges or claims.

(o) Ownership of the General Partner Interest and Incentive Distribution Rights in the Partnership . The General Partner is the sole general partner of the Partnership with a 2% general partner interest and 100% of the Incentive Distribution Rights in the Partnership; such general partner interest and Incentive Distribution Rights have been duly authorized and validly issued in accordance with the limited partnership agreement of the Partnership (the “ Partnership Agreement ”) and, in the case of the Incentive Distribution Rights, are fully paid (to the extent required under the Partnership Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 17-607 of the Delaware LP Act); and the General Partner owns such general partner interest and Incentive Distribution Rights, in each case, free and clear of all liens, encumbrances, security interests, charges or claims.

(p) Ownership of the Partnership’s Common Units by NuStar Holdings. Riverwalk Holdings and NuStar GP, direct wholly owned subsidiaries of NuStar Holdings, own 10,213,894 and 6,416 Common Units, respectively, in the Partnership; such limited partner interests have been duly authorized and validly issued in accordance with the Partnership Agreement and are fully paid (to the extent required under the Partnership Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 17-607 of the Delaware LP Act); and Riverwalk Holdings and NuStar GP own such limited partner interests free and clear of all liens, encumbrances, security interests, charges or claims.

8

(q) Ownership of GP, Inc. by the Partnership . The Partnership owns 100% of the issued and outstanding capital stock of GP, Inc.; such shares of capital stock have been duly authorized and validly issued in accordance with the certificate of incorporation and bylaws of GP, Inc., as amended to date, and are fully paid and nonassessable; and the Partnership owns such shares of capital stock free and clear of all liens, encumbrances, security interests, charges or claims.

(r) Ownership of the General Partner Interest in NuStar Logistics . GP, Inc. is the sole general partner of NuStar Logistics with a 0.01% general partner interest in NuStar Logistics; such general partner interest has been duly authorized and validly issued in accordance with the limited partnership agreement of NuStar Logistics (the “ NuStar Logistics Partnership Agreement ”); and GP, Inc. owns such general partner interest free and clear of all liens, encumbrances, security interests, charges or claims.

(s) Ownership of the Limited Partner Interest in NuStar Logistics. The Partnership is the sole limited partner of NuStar Logistics with a 99.99% limited partner interest in NuStar Logistics; such limited partner interest has been duly authorized and validly issued in accordance with the NuStar Logistics Partnership Agreement and is fully paid (to the extent required under the NuStar Logistics Partnership Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 17-607 of the Delaware LP Act); and the Partnership owns such limited partner interest free and clear of all liens, encumbrances, security interests, charges or claims.

(t) Ownership of LegacyStar Services by the Partnership . The Partnership is the sole member of LegacyStar Services and owns 100% of the issued and outstanding membership interests in LegacyStar Services; such membership interests have been duly authorized and validly issued in accordance with the limited liability company agreement of LegacyStar Services (the “ LegacyStar Services LLC Agreement ”), and are fully paid (to the extent required under the LegacyStar Services LLC Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 18-607 of the Delaware LLC Act); and the Partnership owns such membership interests free and clear of all liens, encumbrances, security interests, charges or claims.

(u) Ownership of NuStar Pipeline GP . LegacyStar Services, a wholly owned subsidiary of the Partnership, is the sole member of NuStar Pipeline GP and owns 100% of the issued and outstanding membership interests in NuStar Pipeline GP; such membership interests have been duly authorized and validly issued in accordance with the limited liability company agreement of NuStar Pipeline GP (the “ NuStar Pipeline GP LLC Agreement ”), and are fully paid (to the extent required under the NuStar Pipeline GP LLC Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 18-607 of the Delaware LLC Act); and LegacyStar Services owns such membership interests free and clear of all liens, encumbrances, security interests, charges or claims.

(v) Ownership of the General Partner Interest in NPP . NuStar Pipeline GP is the sole general partner of NPP with a 1% general partner interest in NPP; such general partner interest has been duly authorized and validly issued in accordance with the

9

limited partnership agreement of NPP (the “ NPP Partnership Agreement ”); and NuStar Pipeline GP owns such general partner interest free and clear of all liens, encumbrances, security interests, charges or claims.

(w) Ownership of the Limited Partner Interest in NPP . The Partnership is the sole limited partner of NPP with a 99% limited partner interest in NPP; such limited partner interest has been duly authorized and validly issued in accordance with the NPP Partnership Agreement and is fully paid (to the extent required under the NPP Partnership Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 17-607 of the Delaware LP Act); and the Partnership owns such limited partner interest free and clear of all liens, encumbrances, security interests, charges or claims.

(x) Ownership of the General Partner Interest in NPOP . NuStar Pipeline GP is the sole general partner of NPOP with a 1% general partner interest in NPOP; such general partner interest has been duly authorized and validly issued in accordance with the limited partnership agreement of NPOP (the “ NPOP Partnership Agreement ”); and NuStar Pipeline GP owns such general partner interest free and clear of all liens, encumbrances, security interests, charges or claims.

(y) Ownership of the Limited Partner Interest in NPOP . NPP is the sole limited partner of NPOP with a 99% limited partner interest in NPOP; such limited partner interest has been duly authorized and validly issued in accordance with the NPOP Partnership Agreement and is fully paid (to the extent required under the NPOP Partnership Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Section 17-607 of the Delaware LP Act); and NPP owns such limited partner interest free and clear of all liens, encumbrances, security interests, charges or claims.

(z) Ownership of the Operating Subsidiaries . Except as set forth on Schedule II hereto, each of NuStar Logistics and NPOP, as applicable, owns 100% of the outstanding capital stock, membership interests or partnership interests, as the case may be, in each of the Operating Subsidiaries; such stock, membership interests or partnership interests have been duly authorized and validly issued in accordance with the applicable certificate of incorporation and bylaws, certificate of formation and limited liability company agreement or certificate of limited partnership and partnership agreement of each Operating Subsidiary, as the case may be (collectively, the “ Operating Subsidiaries Operative Documents ” and, as to each individual Operating Subsidiary, the “ Operating Subsidiary Operative Document ”), except where the failure of such stock, membership interests or partnership interests to be so duly authorized and validly issued would not, individually or in the aggregate, have a Material Adverse Effect, and, except in the case of the general partner interests, are fully paid (to the extent required under the applicable Operating Subsidiary Operative Document) and nonassessable (except as such nonassessability may be affected by matters described in Section 18-607 of the Delaware LLC Act or Section 17-607 of the Delaware LP Act, as the case may be); and each of NuStar Logistics and NPOP, as applicable, own all such stock, membership interests or partnership interests, as the case may be, free and clear of all liens, encumbrances, security interests, charges or claims (collectively, “ Liens ”).

10

(aa) No Other Subsidiaries . The Partnership does not own or control, directly or indirectly, any corporation, association or other entity other than the subsidiaries listed on Schedule II hereto. None of the subsidiaries of the Partnership (other than NuStar Logistics, NPOP, NuStar Asphalt, NuStar Terminals Operations Partnership L.P., a Delaware limited partnership formerly known as Support Terminals Operating Partnership, L.P. (“ NTOP ”) and Shore Terminals LLC, a Delaware limited liability company (“ Shore Terminals ”)) is a “ significant subsidiary ” (as defined in Rule 405).

(bb) Capitalization . The capitalization of the Partnership on a consolidated basis as of December 31, 2007 was as set forth in the Preliminary Prospectus under “Capitalization.”

(cc) Enforceability of Indenture. The execution and delivery of, and the performance by each of NuStar Logistics, the Partnership and NPOP of their respective obligations under the Indenture have been duly and validly authorized by each of NuStar Logistics, the Partnership and NPOP, and, at the Delivery Date, the Indenture will be duly qualified under the Trust Indenture Act of 1939, as amended, and the Rules and Regulations of the Commission thereunder (collectively, the “ Trust Indenture Act ”), and the Indenture, assuming due authorization, execution and delivery thereof by the Trustee, when executed and delivered by each of NuStar Logistics, the Partnership and NPOP, will constitute a valid and legally binding agreement of the Partnership and NPOP (to the extent set forth in the Supplemental Indenture) and NuStar Logistics enforceable against each of NuStar Logistics, the Partnership and NPOP in accordance with its terms; provided that , the enforceability thereof may be limited by bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium and similar laws relating to or affecting creditors’ rights generally and by general principles of equity (regardless of whether such enforceability is considered in a proceeding in equity or at law).

(dd) Valid Issuance of Notes. The Notes have been duly authorized for issuance and sale to the Underwriters, and, when executed by NuStar Logistics and authenticated by the Trustee in accordance with the provisions of the Indenture and delivered to and paid for by the Underwriters in accordance with the terms of this Agreement, will have been duly executed and delivered by NuStar Logistics, and will constitute the valid and legally binding obligations of NuStar Logistics entitled to the benefits of the Indenture and enforceable against NuStar Logistics in accordance with their terms; provided that , the enforceability thereof may be limited by bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium and similar laws relating to or affecting creditors’ rights generally and by general principles of equity (regardless of whether such enforceability is considered in a proceeding in equity or at law).

(ee) Valid Issuance of the Guarantee . The Guarantee to be endorsed on the Notes by the Partnership and NPOP has been duly authorized by NuStar GP on behalf of the Partnership and by NuStar Pipeline GP on behalf of NPOP and, on the Delivery Date, will have been duly executed and delivered by the Partnership and NPOP; when the

11

Notes have been issued, executed and authenticated in accordance with the Indenture, including endorsement of the Notes by the Partnership and NPOP, and delivered to and paid for by the Underwriters in accordance with the terms of this Agreement, the Guarantee will constitute the valid and legally binding obligation of the Partnership and NPOP entitled to the benefits of the Indenture and enforceable against the Partnership and NPOP in accordance with its terms; provided that , the enforceability thereof may be limited by bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium and similar laws relating to or affecting creditors’ rights generally and by general principles of equity (regardless of whether such enforceability is considered in a proceeding in equity or at law).

(ff) No Preemptive Rights, Registration Rights or Options . Except as identified in the most recent Preliminary Prospectus and the Prospectus, there are no (i) preemptive rights or other rights to subscribe for or to purchase, nor any restriction upon the voting or transfer of, any equity securities of the Partnership Parties; or (ii) outstanding options or warrants to purchase any securities of the Partnership Parties. Neither the filing of the Registration Statement nor the offering or sale of the Securities as contemplated by this Agreement gives rise to any rights for or relating to the registration of any securities of the Partnership Parties.

(gg) Authority and Authorization . At the Delivery Date, all corporate, partnership and limited liability company action, as the case may be, required to be taken by any of the Partnership Entities or any of their respective unitholders, stockholders, members or partners for the authorization, sale and delivery of the Securities, the execution and delivery of the Organizational Documents and the consummation of the transactions contemplated by this Agreement and the Indenture, shall have been validly taken.

(hh) Authorization, Execution and Delivery of this Agreement . This Agreement has been duly authorized and validly executed and delivered by each of the Partnership Parties.

(ii) Authorization, Execution, Delivery and Enforceability of Certain Agreements . At or before the Delivery Date, the Organizational Documents will have been duly authorized, executed and delivered by the Partnership Entities party thereto and, assuming the due authorization, valid execution and delivery by the other parties thereto, each will be a valid and legally binding agreement of the Partnership Entities party thereto, enforceable against such parties in accordance with its terms; provided that , with respect to each agreement described in this Section 1(ii), the enforceability thereof may be limited by bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium and similar laws relating to or affecting creditors’ rights generally and by general principles of equity (regardless of whether such enforceability is considered in a proceeding in equity or at law); provided further ; that the indemnity, contribution and exoneration provisions contained in any of such agreements may be limited by applicable laws and public policy.

12

(jj) No Conflicts . None of the offering and sale by NuStar Logistics of the Notes, the execution, delivery and performance of this Agreement by the Partnership Parties and the Organizational Documents, the Guarantee and the Indenture by the Partnership Entities that are parties thereto or the consummation of any other transactions contemplated by this Agreement, the Organizational Documents, the Guarantee or the Indenture (i) conflicts with or will conflict with, or constitutes or will constitute a violation of, the certificate of limited partnership or agreement of limited partnership, certificate of formation or limited liability company agreement, the charter or bylaws, or any other organizational documents of any of the Partnership Entities, (ii) conflicts with or will conflict with, or constitutes or will constitute a breach or violation of, or a default (or an event that, with notice or lapse of time or both, would constitute such a default) under, any indenture, contract, lease, mortgage, deed of trust, note agreement, loan agreement or other agreement, obligation, condition, covenant or instrument to which any of the Partnership Entities is a party or by which any of them are bound or to which any of their respective properties is subject, (iii) violates or will violate any statute, law, rule or regulation, or any judgment, order or decrees of any court, regulatory body, administrative agency, governmental body, arbitrator or other authority having jurisdiction over any of the Partnership Entities or any of their properties or assets, or (iv) will result in the creation or imposition of any Lien upon any property or assets of any of the Partnership Entities, except, in the case of clauses (ii), (iii) and (iv), for such conflicts, breaches, violations, defaults, Liens, charges or encumbrances as would not, individually or in the aggregate, have a Material Adverse Effect, or could materially impair the ability of any of the Partnership Entities to perform their respective obligations under this Agreement, the Guarantee or the Indenture.

(kk) No Consents . No permit, consent, approval, authorization, order, registration, filing or qualification of or with any court, governmental agency or body is required in connection with the execution and delivery of this Agreement by the Partnership Parties, the offer and sale of the Notes by NuStar Logistics, the execution and delivery of the Guarantee by the Partnership and NPOP or the execution, delivery and performance of the Indenture by the Partnership Entities that are parties thereto, except for (i) such permits, consents, approvals and similar authorizations required under the Securities Act, the Securities Exchange Act of 1934, as amended (the “ Exchange Act ”), the Trust Indenture Act and state securities or “Blue Sky” laws, (ii) such consents that have been, or prior to the Delivery Date will be, obtained, (iii) such consents that, if not obtained, would not have a Material Adverse Effect and (iv) as disclosed in the most recent Preliminary Prospectus and the Prospectus.

(ll) No Defaults . None of the Partnership Entities is in (i) violation of its agreement of limited partnership, limited liability company agreement, certificate of incorporation or bylaws or other organizational documents, or of any law, statute, ordinance, administrative or governmental rule or regulation applicable to it or of any decree of any court or governmental agency or body having jurisdiction over it or (ii) breach or default (or an event which, with notice or lapse of time or both, would constitute such an event) in the performance of any term, covenant or condition contained in any bond, debenture, note or any other evidence of indebtedness or in any agreement, indenture, lease or other instrument to which it is a party or by which it or any of its

13

properties is subject which breach, default or violation would, if continued, have a Material Adverse Effect or could materially impair the ability of any of the Partnership Entities to perform their respective obligations under this Agreement, the Guarantee or the Indenture.

(mm) Conformity of Securities to Description in the most recent Preliminary Prospectus and Prospectus . The Securities conform in all material respects to the description thereof contained in the most recent Preliminary Prospectus and Prospectus.

(nn) No Integration . None of the Partnership Parties has sold or issued any securities that would be integrated with the offering of the Securities contemplated by this Agreement pursuant to the Securities Act, the Rules and Regulations or the interpretations thereof by the Commission.

(oo) No Material Adverse Change . None of the Partnership Entities has sustained, since the date of the latest audited financial statements included in the most recent Preliminary Prospectus and the Prospectus any loss or interference with its business from fire, explosion, flood or other calamity, whether or not covered by insurance, or from any labor dispute or court or governmental action, order or decree, and since such date, there has not been any change in the capitalization or long-term debt of any of the Partnership Entities or any adverse change, or any development involving a prospective adverse change, in or affecting the condition or otherwise, results of operations, unitholders’ or stockholders’ equity, properties, management, business or prospects of any of the Partnership Entities taken as a whole, in each case except as would not, in the aggregate, reasonably be expected to have a Material Adverse Effect. Since the date of the latest audited financial statements included in the most recent Preliminary Prospectus and the Prospectus, none of the Partnership Entities has incurred any liability or obligation, direct, indirect or contingent, or entered into any transactions not in the ordinary course of business, that, individually or in the aggregate, is material to any of the Partnership Entities, taken as a whole, otherwise than as set forth or contemplated in the most recent Preliminary Prospectus and the Prospectus.

(pp) Conduct of Business . Since the date as of which information is given in the most recent Preliminary Prospectus and the Prospectus, none of the Partnership Entities have (i) incurred any liability or obligation, direct or contingent, other than liabilities and obligations that were incurred in the ordinary course of business, (ii) entered into any material transaction not in the ordinary course of business or (iii) declared, paid or made any dividend or distribution on any class of security, except in the ordinary course consistent with past practice.

(qq) Financial Statements . The historical financial statements (including the related notes) included in the most recent Preliminary Prospectus and the Prospectus (and any amendment or supplement thereto) comply as to form in all material respects with the requirements of Regulation S-X under the Securities Act and present fairly the financial condition, results of operations and cash flows of the entities purported to be shown thereby at the dates and for the periods indicated and have been prepared in conformity with accounting principles generally accepted in the United States applied on a consistent

14

basis throughout the periods involved. The summary historical and financial data included or incorporated by reference in the most recent Preliminary Prospectus and the Prospectus (and any amendment or supplement thereto) under the captions “Summary – NuStar Energy Summary Consolidated Historical Financial and Operating Data,” “Ratio of Earnings to Fixed Charges,” “Capitalization,” “Selected Financial Data” and “Management’s Discussion and Analysis of Financial Condition and Results of Operations” are accurately presented in all material respects and prepared on a basis consistent with the audited and unaudited historical consolidated financial statements from which such data has been derived.

(rr) Statistical and Market-Related Data . The financial, statistical and market-related data included or incorporated by reference in the most recent Preliminary Prospectus and the Prospectus under the captions “Summary – Recent Developments,” “Risk Factors,” “Management’s Discussion and Analysis of Financial Condition and Results of Operations” and “Business, Risk Factors and Properties” and the consolidated financial statements of the Partnership and its subsidiaries included in the most recent Preliminary Prospectus and the Prospectus are based on or derived from sources that the Partnership believes to be reliable and accurate in all material respects and the Partnership has obtained the written consent to the use of such data from such sources to the extent required.

(ss) Independent Registered Public Accounting Firm . KPMG LLP, who has certified certain financial statements of the Partnership and its consolidated subsidiaries, whose reports appear in the most recent Preliminary Prospectus and the Prospectus and who has delivered the initial letter referred to in Section 6(g) hereof, is an independent registered public accounting firm as required by the Securities Act and the Rules and Regulations was an independent registered public accounting firm as required by the Securities Act and the Rules and Regulations during the periods covered by the financial statements on which they reported contained in the most recent Preliminary Prospectus and the Prospectus.

(tt) Title to Properties . At the Delivery Date, each of the Partnership Parties will have good and indefeasible title to all real property and good and marketable title to all personal property described in the most recent Preliminary Prospectus and the Prospectus as being owned by them, in each case free and clear of all liens, encumbrances and defects, except (i) such as are described in the most recent Preliminary Prospectus and the Prospectus and (ii) such as do not materially interfere with the use of such properties taken as a whole as they have been used in the past and are proposed to be used in the future as described in the most recent Preliminary Prospectus and the Prospectus; all real property and buildings held under lease or license by the Partnership Entities are held by them under valid and subsisting and enforceable leases or licenses with such exceptions as do not materially interfere with the use of such properties taken as a whole as they have been used in the past and are to be used in the future as described in the most recent Preliminary Prospectus and the Prospectus. For purposes of this Agreement, the phrase “good and indefeasible title” to all real property shall mean, with respect to any real property interest, and subject to the terms, conditions, and provisions contained in the realty deeds and leases creating such real property interest, that the

15

ownership, rights, possession and title in the jurisdiction and locale where the real property interest is located, is in each case legally sufficient in all material respects to conduct the business and operations of the Partnership Entities as described or incorporated by reference in the Preliminary Prospectus and the Prospectus under the caption “Business, Risk Factors and Properties,” as such business and operations relate to the location of such real property interest, and is free and clear of all liens, claims, security interests or other encumbrances excepting (in each case) permitted encumbrances, such title defects, and imperfections, limitations, correlative rights, or appurtenant rights or obligations contained in, arising from or created by the instrument under which any of the Partnership Entities hold title to such real property interest or contained in its chain of title thereto, which do not materially and adversely effect current or intended use or operation of the subject real property interest or which are capable of being routinely addressed, cured, avoided or assumed in the ordinary course of business and land management of the Partnership Entities.

(uu) Rights-of Way . At the Delivery Date, each of the Partnership Entities will have such consents, easements, rights-of-way or licenses from any person (“ rights-of-way ”) as are necessary to conduct their business in the manner described in the most recent Preliminary Prospectus and the Prospectus, subject to such qualifications as may be set forth in the most recent Preliminary Prospectus and the Prospectus and except for such rights-of-way which, if not obtained, would not have, individually or in the aggregate, a Material Adverse Effect; each of the Partnership Entities has fulfilled and performed all its material obligations with respect to such rights-of-way and no event has occurred which allows, or after notice or lapse of time would allow, revocation or termination thereof or would result in any impairment of the rights of the holder of any such rights-of-way, except for such revocations, terminations and impairments that would not have a Material Adverse Effect; and, except as described in the most recent Preliminary Prospectus and the Prospectus, none of such rights-of-way contains any restriction that is materially burdensome to the Partnership Entities considered as a whole.

(vv) Insurance . The Partnership Entities maintain insurance covering their properties, operations, personnel and businesses against such losses and risks as are reasonably adequate to protect them and their businesses in a manner consistent with other businesses similarly situated. None of the Partnership Entities has received notice from any insurer or agent of such insurer that material capital improvements or other material expenditures will have to be made in order to continue such insurance as of the Delivery Date, and all such insurance is outstanding and duly in force on the date hereof and will be outstanding and duly in force on the Delivery Date.

(ww) Investment Company . None of the Partnership Entities is, and as of the Delivery Date and, after giving effect to the offer and sale of the Securities and the application of the proceeds therefrom as described under “Use of Proceeds” in the most recent Preliminary Prospectus and the Prospectus, none of them immediately after the Delivery Date will be, an “investment company” or a company “controlled by” an “investment company” within the meaning of such term under the Investment Company Act of 1940, as amended (the “ Investment Company Act ”), and the rules and regulations of the Commission thereunder.

16

(xx) Litigation . Except as described in the most recent Preliminary Prospectus and the Prospectus, there are no legal or governmental proceedings pending to which any of the Partnership Entities is a party or of which any property or assets of any of the Partnership Entities are subject that could, in the aggregate, reasonably be expected to have a Material Adverse Effect or could, in the aggregate, reasonably be expected to have a material adverse effect on the performance of this Agreement or the consummation of the transactions contemplated hereby, and, to the Partnership’s knowledge, no such proceedings are threatened or contemplated by governmental authorities or others.

(yy) Legal Proceedings or Contracts to be Described or Filed . There are no legal or governmental proceedings or contracts or other documents of a character required to be described in the Registration Statement, the most recent Preliminary Prospectus or the Prospectus or, in the case of documents, to be filed as exhibits to the Registration Statement, that are not described and filed as required. None of the Partnership Entities has knowledge that any other party to any such contract, agreement or arrangement has any intention not to render full performance as contemplated by the terms thereof; and that statements made or incorporated by reference in the most recent Preliminary Prospectus and the Prospectus under the captions “Risk Factors,” “Management’s Discussion and Analysis of Financial Condition and Results of Operations,” “Business, Risk Factors and Properties” and “Legal Proceedings” insofar as they purport to constitute summaries of the terms of statutes, rules or regulations, legal or governmental proceedings or contracts and other documents, constitute accurate summaries of the terms of such statutes, rules and regulations, legal and governmental proceedings and contracts and other documents in all material respects.

(zz) Certain Relationships and Related Transactions . Except as described in the most recent Preliminary Prospectus and the Prospectus, no relationship, direct or indirect, exists between or among the Partnership Entities, on the one hand, and the directors, officers, equityholders, customers or suppliers of the any of the Partnership Entities, on the other hand, that is required to be described in the most recent Preliminary Prospectus or the Prospectus which is not so described.

(aaa) No Labor Dispute . No labor disturbance by the employees of any of the Partnership Entities exists or, to the knowledge of the Partnership, is imminent that could reasonably be expected to have a Material Adverse Effect.

(bbb) ERISA . As of the Delivery Date, (i) each “employee benefit plan” (within the meaning of Section 3(3) of the Employee Retirement Income Security Act of 1974, as amended (“ ERISA ”)) for which any of the Partnership Entities or any member of the “Controlled Group” (defined as any organization which is a member of a controlled group of corporations within the meaning of Section 414 of the Internal Revenue Code of 1986, as amended (the “ Code ”)) of any of the Partnership Entities would have any liability (each a “ Plan ”) has been maintained in all material respects in compliance with its terms and with the material requirements of all applicable statutes, rules and

17

regulations including ERISA and the Code; (ii) with respect to each Plan subject to Title IV of ERISA (a) no “reportable event” (within the meaning of Section 4043(c) of ERISA and for which the 30-day reporting requirement has not been waived) has occurred or is reasonably expected to occur, (b) no “accumulated funding deficiency” (within the meaning of Section 302 of ERISA or Section 412 of the Code), whether or not waived, has occurred or is reasonably expected to occur, (c) the fair market value of the assets under each Plan exceeds the present value of all benefits accrued under such Plan (determined on an ongoing basis based on those assumptions used to fund such Plan) and (d) none of the Partnership Entities or any member of the Controlled Group of any of the Partnership Entities has incurred, or reasonably expects to incur, any liability under Title IV of ERISA (other than contributions to the Plan or premiums to the PBGC in the ordinary course and without default) in respect of a Plan (including a “multiemployer plan,” within the meaning of Section 4001(c)(3) of ERISA), in each case that could reasonably be expected to have a Material Adverse Effect; and (iii) each Plan that is intended to be qualified under Section 401(a) of the Code has been determined by the Internal Revenue Service to be so qualified and nothing has occurred, whether by action or by failure to act, which would cause the loss of such qualification.

(ccc) Tax Returns . Each of the Partnership Entities has filed all federal, state, local and foreign income and franchise tax returns required to be filed through the date hereof, subject to permitted extensions, and have paid all taxes due thereon, and no tax deficiency has been determined adversely to any of the Partnership Entities, nor do any of the Partnership Entities have any knowledge of any tax deficiencies that could, in the aggregate, reasonably be expected to have a Material Adverse Effect.

(ddd) Books and Records; Accounting Controls . Each of the Partnership Entities (i) makes and keeps books, records and accounts, which, in reasonable detail, accurately and fairly reflect transactions and dispositions of assets and (ii) maintains and has maintained effective internal control over financial reporting as defined in Rule 13a-15 under the Exchange Act and a system of internal accounting controls sufficient to provide reasonable assurance that (A) transactions are executed in accordance with management’s general or specific authorization; (B) transactions are recorded as necessary to permit preparation of financial statements in conformity with accounting principles generally accepted in the United States and to maintain accountability for its assets; (C) access to assets is permitted only in accordance with management’s general or specific authorization; and (D) the recorded accountability for assets is compared with existing assets at reasonable intervals and appropriate action is taken with respect to any differences.

(eee) Disclosure Controls and Procedures . (i) The Partnership has established and maintains disclosure controls and procedures (as such term is defined in Rule 13a-15 under the Exchange Act), (ii) such disclosure controls and procedures are designed to ensure that the information required to be disclosed by the Partnership in the reports it files or will file or submit under the Exchange Act, as applicable, is accumulated and communicated to management of the Partnership including its respective principal executive officers and principal financial officers, as appropriate, to allow such officers to make timely decisions regarding required disclosure and (iii) such disclosure controls and procedures are effective in all material respects to perform the functions for which they were established.

18

(fff) No Changes in Internal Controls . Since the date of the most recent balance sheet of the Partnership and its consolidated subsidiaries reviewed or audited by KPMG LLP and the audit committee of the board of directors of NuStar GP, (i) the Partnership has not been advised of (A) any significant deficiencies in the design or operation of internal controls that could adversely affect the ability of any such entities to record, process, summarize and report financial data, or any material weaknesses in internal controls or (B) any fraud, whether or not material, that involves management or other employees who have a significant role in the internal controls of any such entity, and (ii) since that date, there have been no significant changes in internal controls or in other factors that could significantly affect internal controls, including any corrective actions with regard to significant deficiencies and material weaknesses.

(ggg) Sarbanes-Oxley Act of 2002 . There is and has been no failure on the part of any of NuStar GP’s directors or officers, in their capacities as such, to comply in all material respects with the provisions of the Sarbanes-Oxley Act of 2002 and the rules and regulations promulgated in connection therewith (the “ Sarbanes-Oxley Act ”).

(hhh) Critical Accounting Policies . The section entitled “Management’s Discussion and Analysis of Financial Condition and Results of Operations—Critical Accounting Policies” in the most recent Preliminary Prospectus and the Prospectus accurately and fully describes (A) the accounting policies that the Partnership believes are the most important in the portrayal of the financial condition and results of operations of the Partnership, and that require management’s most difficult, subjective or complex judgments (“ Critical Accounting Policies ”); (B) the judgments and uncertainties affecting the application of Critical Accounting Policies; and (C) the likelihood that materially different amounts would be reported under different conditions or using different assumptions and an explanation thereof.

(iii) Permits . Each of the Partnership Entities has such permits, consents, licenses, franchises, certificates and authorizations of governmental or regulatory authorities (“ Permits ”) as are necessary to own its properties and to conduct its businesses in the manner described in the most recent Preliminary Prospectus and the Prospectus, subject to such qualifications as may be set forth in the most recent Preliminary Prospectus and the Prospectus and except for such permits which, if not obtained, would not, individually or in the aggregate, reasonably be expected to have a Material Adverse Effect; each of the Partnership Entities has fulfilled and performed all its material obligations with respect to the Permits which are due to have been fulfilled and performed by such date, and no event has occurred that allows, or after notice or lapse of time would allow, revocation or termination thereof or results in any other impairment of the rights of the holder of any such Permits, except for any of the foregoing that would not reasonably be expected to have a Material Adverse Effect; and, except as described in the most recent Preliminary Prospectus and the Prospectus, none of the Permits contain any restriction that is materially burdensome to the Partnership Entities considered as a whole.

19

(jjj) Environmental Compliance . Each of the Partnership Entities (i) is in compliance with any and all applicable federal, state and local laws and regulations relating to the protection of human health and safety and the environment or imposing liability or standards of conduct concerning any Hazardous Materials (as defined below) (“ Environmental Laws ”), (ii) has received all permits required of such entity under applicable Environmental Laws to conduct its businesses, (iii) are in compliance with all terms and conditions of any such permits and (iv) does not have any liability in connection with the release into the environment of any Hazardous Material, except where such noncompliance with Environmental Laws, failure to receive required permits, failure to comply with the terms and conditions of such permits or liability in connection with such releases would not, individually or in the aggregate, have a Material Adverse Effect. The term “ Hazardous Material ” means (A) any “hazardous substance” as defined in the Comprehensive Environmental Response, Compensation and Liability Act of 1980, as amended, (B) any “hazardous waste” as defined in the Resource Conservation and Recovery Act, as amended, (C) any petroleum or petroleum product, (D) any polychlorinated biphenyl and (E) any pollutant or contaminant or hazardous, dangerous or toxic chemical, material, waste or substance regulated under or within the meaning of any other Environmental Law.

(kkk) No Restrictions on Distributions . None of the Operating Subsidiaries is currently prohibited, directly or indirectly, from paying any dividends or other distributions, as applicable, to the Partnership, from repaying to the Partnership any loans or advances to such Operating Subsidiary from the Partnership or from transferring any of such Operating Subsidiary’s property or assets to the Partnership or any other Operating Subsidiary of the Partnership, except as described in or contemplated by (A) the most recent Preliminary Prospectus and the Prospectus, (B) the organizational documents of the Operating Subsidiaries or (C) the periodic and current reports filed by the Partnership with the Commission pursuant to the Exchange Act.

(lll) No Distribution of Other Offering Materials . None of the Partnership Entities has distributed and, prior to the later to occur of the Delivery Date and completion of the distribution of the Notes, will distribute any offering material in connection with the offering and sale of the Notes other than any Preliminary Prospectus, the Prospectus and any Issuer Free Writing Prospectus to which the Representatives have consented in accordance with Section 1(i) or 4(a)(vi) or as set forth on Schedule III hereto.

(mmm) Market Stabilization . The Partnership has not taken and will not take, directly or indirectly, any action designed to or that has constituted or that could reasonably be expected to cause or result in the stabilization or manipulation of the price of any security of the Partnership or NuStar Logistics to facilitate the sale or resale of the Securities.

Any certificate signed by any officer on behalf of the Partnership and delivered to the Representatives or counsel for the Underwriters in connection with the offering of the Securities shall be deemed a representation and warranty by the Partnership, as to matters covered thereby, to each Underwriter.

20

2. Purchase of the Securities by the Underwriters . On the basis of the representations and warranties contained in, and subject to the terms and conditions of, this Agreement, NuStar Logistics agrees to issue and sell the Notes to the several Underwriters, and each of the Underwriters, severally and not jointly, agrees to purchase the principal amount of Notes from NuStar Logistics set forth opposite that Underwriter’s name in Schedule I hereto at a price equal to 99.152% of the principal amount thereof plus accrued interest, if any, from the Delivery Date. NuStar Logistics shall not be obligated to deliver any of the Notes except upon payment for all the Notes to be purchased as provided herein.

3. Delivery of and Payment for the Securities . Delivery of and payment for the Notes shall be made at 10:00 A.M., New York City time, on the third full business day following the date of this Agreement or at such other date or place as shall be determined by agreement between the Representatives and the Partnership (such date and time are sometimes referred to as the “ Delivery Date ”). Delivery of the Notes shall be made to the Representatives for the account of each Underwriter against payment by the several Underwriters through the Representatives and of the respective aggregate purchase prices of the Notes being sold by NuStar Logistics to or upon the order of NuStar Logistics of the purchase price by wire transfer in immediately available funds to the accounts specified by the Partnership. Time shall be of the essence, and delivery at the time and place specified pursuant to this Agreement is a further condition of the obligation of each Underwriter hereunder. NuStar Logistics shall deliver the Notes through the facilities of the Depository Trust Company unless the Representatives shall otherwise instruct.

4. Further Agreements of the Partnership Parties.

(a) Each of the Partnership Parties agrees:

(i) Preparation of Prospectus and Registration Statement . To prepare the Prospectus in a form approved by the Representatives and to file such Prospectus pursuant to Rule 424(b) under the Securities Act not later than the Commission’s close of business on the second business day following the execution and delivery of this Agreement; to make no further amendment or any supplement to the Registration Statement or the Prospectus prior to the Delivery Date except as provided herein; to advise the Representatives, promptly after it receives notice thereof, of the time when any amendment or supplement to the Registration Statement or the Prospectus has been filed and to furnish or make available to the Representatives copies thereof; to file promptly all reports and any definitive proxy or information statements required to be filed by each of the Partnership Parties with the Commission pursuant to Section 13(a), 13(c), 14 or 15(d) of the Exchange Act subsequent to the date of the Prospectus and for so long as the delivery of a prospectus is required in connection with the offering or sale of the Securities; to advise the Representatives, promptly after it receives notice thereof, of the issuance by the Commission of any stop order or of any order preventing or suspending the use of the Prospectus or any Issuer Free Writing Prospectus, of the suspension of the qualification of the Securities for offering or sale in any jurisdiction, of the initiation or threatening of any proceeding or examination for any such purpose, of any notice from the

21

Commission objecting to the use of the form of the Registration Statement or any post-effective amendment thereto or of any request by the Commission for the amending or supplementing of the Registration Statement, the Prospectus or any Issuer Free Writing Prospectus or for additional information; and, in the event of the issuance of any stop order or of any order preventing or suspending the use of the Prospectus or any Issuer Free Writing Prospectus or suspending any such qualification, to use promptly its best efforts to obtain its withdrawal;

(ii) Payment of Filing Fees . To pay the applicable Commission filing fees relating to the Securities within the time required by Rule 456(b)(1) without regard to the proviso therein;

(iii) Signed Copies of Registration Statement . To furnish promptly to the Representatives and to counsel for the Underwriters a signed copy of the Registration Statement as originally filed with the Commission, and each amendment thereto filed with the Commission, including all consents and exhibits filed therewith;

(iv) Copies of Documents to Underwriters . To deliver promptly to the Representatives such number of the following documents as the Representatives shall reasonably request: (A) conformed copies of the Registration Statement as originally filed with the Commission and each amendment thereto (in each case excluding exhibits), (B) each Preliminary Prospectus, the Prospectus and any amended or supplemented Prospectus, (C) each Issuer Free Writing Prospectus and (D) any document incorporated by reference in any Preliminary Prospectus or the Prospectus; and, if the delivery of a prospectus is required at any time after the date hereof in connection with the offering or sale of the Securities or any other securities relating thereto and if at such time any events shall have occurred as a result of which the Prospectus as then amended or supplemented would include an untrue statement of a material fact or omit to state any material fact necessary in order to make the statements therein, in the light of the circumstances under which they were made when such Prospectus is delivered, not misleading, or, if for any other reason it shall be necessary to amend or supplement the Prospectus or to file under the Exchange Act any document incorporated by reference in the Prospectus in order to comply with the Securities Act or the Exchange Act, to notify the Representatives and, upon their request, to file such document and to prepare and furnish without charge to each Underwriter and to any dealer in securities as many copies as the Representatives may from time to time reasonably request of an amended or supplemented Prospectus that will correct such statement or omission or effect such compliance;

(v) Filing of Amendment or Supplement . To file promptly with the Commission any amendment or supplement to the Registration Statement or the Prospectus or any new, replacement registration statement that may, in the judgment of the Partnership or, for so long as the delivery of a prospectus is required in connection with the offering or sale of the Securities, the Representatives, be required by the Securities Act or requested by the

22

Commission; prior to filing with the Commission any amendment or supplement to the Registration Statement or to the Prospectus or any new, replacement registration statement, any document incorporated by reference in the Prospectus or any amendment to any document incorporated by reference in the Prospectus, to furnish a copy thereof to the Representatives and counsel for the Underwriters and obtain the consent of the Representatives to the filing for so long as the delivery of a prospectus is required in connection with the offering or sale of the Notes; and to furnish to the Underwriters such number of copies of such new registration statement, amendment or supplement as the Underwriters may reasonably request, use its commercially reasonable efforts to cause such new registration statement or amendment to be declared effective as soon as practicable and, in any such case, to promptly notify the Representatives of such filings and effectiveness;

(vi) Issuer Free Writing Prospectus . To prepare a pricing term sheet, containing solely a description of final terms of the Securities and the offering thereof, in the form approved by you and attached as Schedule IV hereto and to file such pricing term sheet pursuant to Rule 433 under the Securities Act within the time required by such rule, and not to make any offer relating to the Securities that would constitute an Issuer Free Writing Prospectus without the prior written consent of the Representatives; to retain in accordance with the Rules and Regulations all Issuer Free Writing Prospectuses not required to be filed pursuant to the Rules and Regulations; and if at any time after the date hereof any events shall have occurred as a result of which any Issuer Free Writing Prospectus, as then amended or supplemented, would conflict with the information in the Registration Statement, the most recent Preliminary Prospectus or the Prospectus or would include an untrue statement of a material fact or omit to state any material fact necessary in order to make the statements therein, in the light of the circumstances under which they were made, not misleading, or, if for any other reason it shall be necessary to amend or supplement any Issuer Free Writing Prospectus, to notify the Representatives and, upon their request, to file such document and to prepare and furnish without charge to each Underwriter as many copies as the Representatives may from time to time reasonably request of an amended or supplemented Issuer Free Writing Prospectus that will correct such conflict, statement or omission or effect such compliance;

(vii) Reports to Security Holders . As soon as practicable after the Effective Date (it being understood that the Partnership shall have until at least 410 days or, if the fourth quarter following the fiscal quarter that includes the Effective Date is the last fiscal quarter of the Partnership’s fiscal year, 455 days after the end of the Partnership’s current fiscal quarter), to make generally available to the Partnership’s security holders and to deliver to the Representatives an earnings statement of the Partnership and its subsidiaries (which need not be audited) complying with Section 11(a) of the Securities Act and the Rules and Regulations (including, at the option of the Partnership, Rule 158);

23

(viii) Qualifications . Promptly from time to time to take such action as the Representatives may reasonably request to qualify the Securities for offering and sale under the securities laws of such jurisdictions as the Representatives may request and to comply with such laws so as to permit the continuance of sales and dealings therein in such jurisdictions for as long as may be necessary to complete the distribution of the Securities; provided that in connection therewith the Partnership shall not be required to (i) qualify as a foreign limited partnership in any jurisdiction in which it would not otherwise be required to so qualify, (ii) file a general consent to service of process in any such jurisdiction or (iii) subject itself to taxation in any jurisdiction in which it would not otherwise be subject;

(ix) Lock-Up Period . For a period commencing on the date hereof and continuing to and including the 30 days after the date of the Prospectus, not to, directly or indirectly, offer, sell, contract to sell, pledge, grant any option to purchase, make any short sale or otherwise dispose of, except as provided hereunder, any securities that are substantially similar to the Securities without the prior written consent of the Representatives;

(x) Use of Proceeds . To apply the net proceeds from the sale of the Notes being sold by NuStar Logistics as set forth in the Prospectus;

(b) Use of “Issuer Information” in “Free Writing Prospectus . ” Each Underwriter severally agrees that such Underwriter shall not include any “issuer information” (as defined in Rule 433) in any “free writing prospectus” (as defined in Rule 405) used or referred to by such Underwriter without the prior consent of the Partnership (any such issuer information with respect to whose use the Partnership has given its consent, “ Permitted Issuer Information ”); provided that (i) no such consent shall be required with respect to any such issuer information contained in any document filed by the Partnership with the Commission prior to the use of such free writing prospectus; (ii) no such consent shall be required with respect to one or more term sheets relating to the Securities containing customary information and conveyed to the purchasers of Securities and (iii) “issuer information,” as used in this Section 4, shall not be deemed to include information prepared by or on behalf of such Underwriter on the basis of or derived from issuer information.

5. Expenses . The Partnership agrees, whether or not the transactions contemplated by this Agreement are consummated or this Agreement is terminated, that it will pay or cause to be paid all costs, expenses, fees and taxes incident to and in connection with (a) the authorization, issuance, sale and delivery of the Securities and any stamp duties or other taxes payable in that connection, and the preparation and printing of certificates for the Securities; (b) the preparation, printing and filing under the Securities Act of the Registration Statement (including any exhibits thereto), any Preliminary Prospectus, the Prospectus, any Issuer Free Writing Prospectus and any amendment or supplement thereto; (c) the distribution of the Registration Statement (including any exhibits thereto), any Preliminary Prospectus, the Prospectus, any Issuer Free Writing Prospectus and any amendment or supplement thereto, or any document incorporated by reference therein, all as provided in this Agreement; (d) the preparation, printing, authentication, issuance and delivery of certificates for the Securities,

24

including any stamp or transfer taxes in connection with the sale of the Securities; (e) services provided by the transfer agent or registrar; (f) the production and distribution of this Agreement, any supplemental agreement among Underwriters, and any other related documents in connection with the offering, purchase, sale and delivery of the Securities; (g) any review by Financial Industry Regulatory Authority of the terms of sale of the Securities (including related fees and expenses of counsel to the Underwriters); (h) any transfer fees or taxes relating to the transfer of the Securities to the Underwriters; (i) the qualification of the Securities under the securities laws of the several jurisdictions as provided in Section (a)(viii)); (j) the investor presentations on any “road show” undertaken in connection with the marketing of the Securities, including, without limitation, expenses associated with any electronic roadshow, travel and lodging expenses of the Representatives and officers of Partnership and half of the cost of any aircraft chartered in connection with the road show; and (k) all other costs and expenses incident to the performance of the obligations of the Partnership Parties under this Agreement; provided that , except as provided in this Section 5 and in Section 10, the Underwriters shall pay their own costs and expenses, including the costs and expenses of their counsel, any transfer taxes on the Notes that they may sell and the expenses of advertising any offering of the Securities made by the Underwriters.

6. Conditions of Underwriters’ Obligations . The respective obligations of the Underwriters hereunder are subject to the accuracy, when made and on the Delivery Date, of the representations and warranties of the Partnership Parties contained herein, to the accuracy of the statements of the Partnership Parties and the officers of GP, Inc., NuStar GP and NuStar Pipeline GP on behalf of NuStar Logistics, the Partnership and NPOP, respectively made in any certificates delivered pursuant hereto, to the performance by the Partnership Parties of their respective obligations hereunder, and to each of the following additional terms and conditions:

(a) The Prospectus shall have been timely filed with the Commission in accordance with Section 4(a)(i); no stop order suspending the effectiveness of the Registration Statement or preventing or suspending the use of the Prospectus or any Issuer Free Writing Prospectus shall have been issued and no proceeding or examination for such purpose shall have been initiated or threatened by the Commission; any request of the Commission for inclusion of additional information in the Registration Statement or the Prospectus or otherwise shall have been complied with; and the Commission shall not have notified the Partnership of any objection to use of the form of the Registration Statement.

(b) No Underwriter shall have discovered and disclosed to the Partnership on or prior to the Delivery Date that the Registration Statement, the Prospectus or the Pricing Disclosure Package, or any amendment or supplement thereto, contains an untrue statement of a fact which, in the opinion of Baker Botts L.L.P., counsel for the Underwriters, is material or omits to state a fact which, in the opinion of such counsel, is material and is required to be stated therein or is necessary to make the statements therein not misleading.

(c) All corporate, partnership and limited liability company proceedings and other legal matters incident to the authorization, form and validity of this Agreement, the Securities, the Registration Statement, the Prospectus and any Issuer Free Writing

25

Prospectus, and all other legal matters relating to this Agreement and the transactions contemplated hereby shall be reasonably satisfactory in all material respects to counsel for the Underwriters, and the Partnership Parties shall have furnished to such counsel all documents and information that they may reasonably request to enable them to pass upon such matters.

(d) Andrews Kurth LLP shall have furnished to the Representatives its written opinion, as counsel to the Partnership Parties, addressed to the Underwriters and dated the Delivery Date, in form and substance reasonably satisfactory to the Representatives, substantially in the form attached hereto as Exhibit A-1.

(e) Bradley C. Barron, Senior Vice President, General Counsel and Secretary of NuStar GP and GP, Inc. and Senior Vice President and Secretary of NuStar Pipeline GP, shall have furnished to the Representatives a written opinion addressed to the Underwriters and dated the Delivery Date, in form and substance reasonably satisfactory to the Representatives, substantially in the form attached hereto as Exhibit A-2.

(f) The Representatives shall have received from Baker Botts L.L.P., counsel for the Underwriters, such opinion or opinions, dated the Delivery Date, with respect to the sale of the Notes, the Registration Statement, the Prospectus and the Pricing Disclosure Package and other related matters as the Representatives may reasonably require, and the Partnership Parties shall have furnished to such counsel such documents as they reasonably request for the purpose of enabling them to pass upon such matters.

(g) At the time of execution of this Agreement, the Representatives shall have received from KPMG LLP a letter or letters, in form and substance satisfactory to the Representatives, addressed to the Underwriters and dated the date hereof (i) confirming that it is an independent registered public accounting firm within the meaning of the Securities Act and is in compliance with the applicable requirements relating to the qualification of accountants under Rule 2-01 of Regulation S-X of the Commission, and (ii) stating, as of the date hereof (or, with respect to matters involving changes or developments since the respective dates as of which specified financial information is given in the most recent Preliminary Prospectus, as of a date not more than five days prior to the date hereof), the conclusions and findings of such firm with respect to the financial information and other matters ordinarily covered by accountants’ “comfort letters” to underwriters in connection with registered public offerings.

(h) With respect to the letters of KPMG LLP referred to in the preceding paragraph and delivered to the Representatives concurrently with the execution of this Agreement (the “ initial letter ”), the Partnership shall have furnished to the Representatives a letter (the “ bring-down letter ”) of such accountant, addressed to the Underwriters and dated the Delivery Date (i) confirming that it is an independent registered public accounting firm within the meaning of the Securities Act and is in compliance with the applicable requirements relating to the qualification of accountants under Rule 2-01 of Regulation S-X of the Commission, (ii) stating, as of the date of the bring-down letter (or, with respect to matters involving changes or developments since the respective dates as of which specified financial information is given in the Prospectus,

26

as of a date not more than three days prior to the date of the bring-down letter), the conclusions and findings of such firm with respect to the financial information and other matters covered by the initial letter and (iii) confirming in all material respects the conclusions and findings set forth in the initial letter.

(i) NuStar Logistics, the Partnership and NPOP shall have furnished to the Representatives a certificate, dated the Delivery Date, signed on behalf of NuStar Logistics, the Partnership and NPOP by (1) the President and Chief Executive Officer of GP, Inc., NuStar GP and NuStar Pipeline GP and (2) the Senior Vice President, Chief Financial Officer and Treasurer of GP, Inc., NuStar GP and NuStar Pipeline GP, stating that:

(i) The representations, warranties and agreements of the Partnership Parties in Section 1 are true and correct on and as of the Delivery Date, and that each of the Partnership Parties has complied with all of its respective agreements contained herein and satisfied all of the respective conditions on its part to be performed or satisfied hereunder at or prior to the Delivery Date;

(ii) No stop order suspending the effectiveness of the Registration Statement has been issued; and no proceedings or examination for that purpose have been instituted or, to the knowledge of such officers, threatened; and the Commission has not notified the Partnership of any objection to the use of the form of the Registration Statement or any post-effective amendment thereto; and

(iii) They have carefully examined the Registration Statement, the Prospectus and the Pricing Disclosure Package, and nothing has come to their attention that would lead them to believe that, (A) (1) the Registration Statement, as of the Effective Date, (2) the Prospectus, as of its date and on the Delivery Date, or (3) the Pricing Disclosure Package, as of the Applicable Time, did or do contain any untrue statement of a material fact and did or do omit to state a material fact required to be stated therein or necessary to make the statements therein (except in the case of the Registration Statement, in the light of the circumstances under which they were made) not misleading or (B) since the Effective Date, an event has occurred that should have been set forth in a supplement or amendment to the Registration Statement, the Prospectus or any Issuer Free Writing Prospectus that has not been so set forth;

(j) Except as described in the most recent Preliminary Prospectus, (i) none of the Partnership Entities shall have sustained, since the date of the latest audited financial statements included in the most recent Preliminary Prospectus, any loss or interference with its business from fire, explosion, flood or other calamity, whether or not covered by insurance, or from any labor dispute or court or governmental action, order or decree or (ii) since such date there shall not have been any change in the capitalization or long-term debt of any of the Partnership Entities or any change, or any development involving a prospective change, in or affecting the condition (financial or otherwise), results of operations, equity, properties, management, business or prospects of any of the Partnership Entities taken as a whole, the effect of which, in any such case described in

27

clause (i) or (ii), is, in the judgment of the Representatives, so material and adverse as to make it impracticable or inadvisable to proceed with the public offering or the delivery of the Securities being delivered on the Delivery Date on the terms and in the manner contemplated in the Prospectus.

(k) No action shall have been taken and no statute, rule, regulation or order shall have been enacted, adopted or issued by any governmental agency or body which would, as of the Delivery Date, prevent the issuance or sale of the Securities; and no injunction, restraining order or order of any other nature by any federal or state court of competent jurisdiction shall have been issued as of the Delivery Date which would prevent the issuance or sale of the Securities.

(l) Subsequent to the execution and delivery of this Agreement there shall not have occurred any of the following: (i) trading in securities generally on the New York Stock Exchange or the American Stock Exchange or in the over-the-counter market, or trading in any securities of the Partnership on any exchange or in the over-the-counter market, shall have been suspended or materially limited or the settlement of such trading generally shall have been materially disrupted or minimum prices shall have been established on any such exchange or such market by the Commission, by such exchange or by any other regulatory body or governmental authority having jurisdiction, (ii) a banking moratorium shall have been declared by federal or state authorities, (iii) the United States shall have become engaged in hostilities, there shall have been an escalation in hostilities involving the United States or there shall have been a declaration of a national emergency or war by the United States or (iv) there shall have occurred such a material adverse change in general economic, political or financial conditions, including, without limitation, as a result of terrorist activities after the date hereof (or the effect of international conditions on the financial markets in the United States shall be such), as to make it, in the judgment of the Representatives, impracticable or inadvisable to proceed with the public offering or delivery of the Securities being delivered on the Delivery Date on the terms and in the manner contemplated in the Prospectus.

(m) Subsequent to the execution and delivery of this Agreement, if any debt securities of any of the Partnership Entities are rated by any “nationally recognized statistical rating organization,” as that term is defined by the Commission for purposes of Section 3(a)(62) of the Exchange Act, (i) no downgrading shall have occurred in the rating accorded such debt securities (including the Notes) and (ii) no such organization shall have publicly announced that it has under surveillance or review, with possible negative implications, its rating of any securities (including the Notes) of any of the Partnership Entities.

(n) On or before the Applicable Time, the Notes shall have been accorded a rating of not less than BBB- by Standard & Poor’s Rating Group, not less than BBB- by Fitch Ratings Ltd. and not less than Baa3 by Moody’s Investor Service, Inc.

(o) NuStar Logistics, the Partnership and NPOP and the Trustee shall have executed and delivered the Notes, the Guarantee and the Indenture to which each of them is a party.

28

All opinions, letters, evidence and certificates mentioned above or elsewhere in this Agreement shall be deemed to be in compliance with the provisions hereof only if they are in form and substance reasonably satisfactory to counsel for the Underwriters.

7. Indemnification and Contribution.

(a) Each of the Partnership Parties, jointly and severally, shall indemnify and hold harmless each Underwriter, its directors, officers and employees and each person, if any, who controls any Underwriter within the meaning of Section 15 of the Securities Act, from and against any loss, claim, damage or liability, joint or several, or any action in respect thereof (including, but not limited to, any loss, claim, damage, liability or action relating to purchases and sales of the Securities), to which that Underwriter, director, officer, employee or controlling person may become subject, under the Securities Act or otherwise, insofar as such loss, claim, damage, liability or action arises out of, or is based upon, (i) any untrue statement or alleged untrue statement of a material fact contained in (A) any Preliminary Prospectus, the Registration Statement, the Prospectus or in any amendment or supplement thereto, (B) any Issuer Free Writing Prospectus or in any amendment or supplement thereto or (C) any Permitted Issuer Information used or referred to in any “free writing prospectus” (as defined in Rule 405) used or referred to by any Underwriter or (D) any “road show” (as defined in Rule 433) not constituting an Issuer Free Writing Prospectus (a “ Non-Prospectus Road Show ”), (ii) the omission or alleged omission to state in any Preliminary Prospectus, the Registration Statement, the Prospectus, any Issuer Free Writing Prospectus or in any amendment or supplement thereto or in any Permitted Issuer Information or any Non-Prospectus Road Show, any material fact required to be stated therein or necessary to make the statements therein not misleading or (iii) any act or failure to act or any alleged act or failure to act by any Underwriter in connection with, or relating in any manner to, the Securities or the offering contemplated hereby, and which is included as part of or referred to in any loss, claim, damage, liability or action arising out of or based upon matters covered by clause (i) or (ii) above ( provided that no Partnership Party shall be liable under this clause (iii) to the extent that it is determined in a final judgment by a court of competent jurisdiction that such loss, claim, damage, liability or action resulted directly from any such acts or failures to act undertaken or omitted to be taken by such Underwriter through its gross negligence or willful misconduct), and shall reimburse each Underwriter and each such director, officer, employee or controlling person promptly upon demand for any legal or other expenses reasonably incurred by that Underwriter, director, officer, employee or controlling person in connection with investigating or defending or preparing to defend against any such loss, claim, damage, liability or action as such expenses are incurred; provided, however , that no Partnership Party shall be liable in any such case to the extent that any such loss, claim, damage, liability or action arises out of, or is based upon, any untrue statement or alleged untrue statement or omission or alleged omission made in any Preliminary Prospectus, the Registration Statement, the Prospectus, any Issuer Free Writing Prospectus or in any such amendment or supplement thereto or in any Permitted Issuer Information or any Non-Prospectus Road Show, in reliance upon and in conformity with written information concerning such Underwriter furnished to the Partnership through the Representatives by or on behalf of any Underwriter specifically for inclusion therein, which information consists solely of

29

the information specified in Section 7(e). The foregoing indemnity agreement is in addition to any liability which the Partnership Parties may otherwise have to any Underwriter or to any director, officer, employee or controlling person of that Underwriter.

(b) Each Underwriter, severally and not jointly, shall indemnify and hold harmless each of the Partnership Parties, their respective directors, managers, officers and employees, and each person, if any, who controls any of the Partnership Parties within the meaning of Section 15 of the Securities Act, from and against any loss, claim, damage or liability, joint or several, or any action in respect thereof, to which such person may become subject, under the Securities Act or otherwise, insofar as such loss, claim, damage, liability or action arises out of, or is based upon, (i) any untrue statement or alleged untrue statement of a material fact contained in any Preliminary Prospectus, the Registration Statement, the Prospectus, any Issuer Free Writing Prospectus or in any amendment or supplement thereto or in any Non-Prospectus Road Show, or (ii) the omission or alleged omission to state in any Preliminary Prospectus, the Registration Statement, the Prospectus, any Issuer Free Writing Prospectus or in any amendment or supplement thereto or in any Non-Prospectus Road Show, any material fact required to be stated therein or necessary to make the statements therein not misleading, but in each case only to the extent that the untrue statement or alleged untrue statement or omission or alleged omission was made in reliance upon and in conformity with written information concerning such Underwriter furnished to the Partnership through the Representatives by or on behalf of that Underwriter specifically for inclusion therein, which information is limited to the information set forth in Section 7(e). The foregoing indemnity agreement is in addition to any liability that any Underwriter may otherwise have to any of the Partnership Parties or any such director, manager, officer, employee or controlling person.

(c) Promptly after receipt by an indemnified party under this Section 7 of notice of any claim or the commencement of any action, the indemnified party shall, if a claim in respect thereof is to be made against the indemnifying party under this Section 7, notify the indemnifying party in writing of the claim or the commencement of that action; provided, however , that the failure to notify the indemnifying party shall not relieve it from any liability which it may have under Section 7(a) or 7(b) except to the extent it has been materially prejudiced by such failure and, provided, further , that the failure to notify the indemnifying party shall not relieve it from any liability which it may have to an indemnified party otherwise than under this Section 7. If any such claim or action shall be brought against an indemnified party, and it shall notify the indemnifying party thereof, the indemnifying party shall be entitled to participate therein and, to the extent that it wishes, jointly with any other similarly notified indemnifying party, to assume the defense thereof with counsel reasonably satisfactory to the indemnified party. After notice from the indemnifying party to the indemnified party of its election to assume the defense of such claim or action, the indemnifying party shall not be liable to the indemnified party under this Section 7 for any legal or other expenses subsequently incurred by the indemnified party in connection with the defense thereof other than reasonable costs of investigation; provided, however , that the Representatives shall have the right to employ counsel to represent jointly the Representatives and those other

30

Underwriters and their respective directors, officers, employees and controlling persons who may be subject to liability arising out of any claim in respect of which indemnity may be sought by the Underwriters against any of the Partnership Parties under this Section 7 if (i) the Partnership Parties and the Underwriters shall have so mutually agreed; (ii) the Partnership Parties have failed within a reasonable time to retain counsel reasonably satisfactory to the Underwriters; (iii) the Underwriters and their respective directors, officers, employees and controlling persons shall have reasonably concluded that there may be legal defenses available to them that are different from or in addition to those available to the Partnership Parties; or (iv) the named parties in any such proceeding (including any impleaded parties) include both the Underwriters or their respective directors, officers, employees or controlling persons, on the one hand, and the Partnership Parties, on the other hand, and representation of both sets of parties by the same counsel would be inappropriate due to actual or potential differing interests between them, and in any such event the fees and expenses of such separate counsel shall be paid by the Partnership Parties. No indemnifying party shall (i) without the prior written consent of the indemnified parties (which consent shall not be unreasonably withheld), settle or compromise or consent to the entry of any judgment with respect to any pending or threatened claim, action, suit or proceeding in respect of which indemnification or contribution may be sought hereunder (whether or not the indemnified parties are actual or potential parties to such claim or action) unless such settlement, compromise or consent includes an unconditional release of each indemnified party from all liability arising out of such claim, action, suit or proceeding and does not include any findings of fact or admissions of fault or culpability as to the indemnified party, or (ii) be liable for any settlement of any such action effected without its written consent (which consent shall not be unreasonably withheld), but if settled with the consent of the indemnifying party or if there be a final judgment for the plaintiff in any such action, the indemnifying party agrees to indemnify and hold harmless any indemnified party from and against any loss or liability by reason of such settlement or judgment.

(d) If the indemnification provided for in this Section 7 shall for any reason be unavailable to or insufficient to hold harmless an indemnified party under Section 7(a) or 7(b) in respect of any loss, claim, damage or liability, or any action in respect thereof, referred to therein, then each indemnifying party shall, in lieu of indemnifying such indemnified party, contribute to the amount paid or payable by such indemnified party as a result of such loss, claim, damage or liability, or action in respect thereof, (i) in such proportion as shall be appropriate to reflect the relative benefits received by the Partnership, on the one hand, and the Underwriters, on the other hand, from the sale of the Notes or (ii) if the allocation provided by clause (i) above is not permitted by applicable law, in such proportion as is appropriate to reflect not only the relative benefits referred to in clause (i) above but also the relative fault of the Partnership, on the one hand, and the Underwriters, on the other hand, with respect to the statements or omissions that resulted in such loss, claim, damage or liability, or action in respect thereof, as well as any other relevant equitable considerations. The relative benefits received by the Partnership, on the one hand, and the Underwriters, on the other hand, with respect to such sale shall be deemed to be in the same proportion as the total net proceeds from the sale of the Notes purchased under this Agreement (before deducting expenses) received by NuStar Logistics, as set forth in the table on the cover page of the

31

Prospectus, on the one hand, and the total underwriting discounts and commissions received by the Underwriters with respect to the Notes purchased under this Agreement, as set forth in the table on the cover page of the Prospectus, on the other hand. The relative fault shall be determined by reference to whether the untrue or alleged untrue statement of a material fact or omission or alleged omission to state a material fact relates to information supplied by the Partnership Parties or the Underwriters, the intent of the parties and their relative knowledge, access to information and opportunity to correct or prevent such statement or omission. The Partnership Parties and the Underwriters agree that it would not be just and equitable if contributions pursuant to this Section 7(d) were to be determined by pro rata allocation (even if the Underwriters were treated as one entity for such purpose) or by any other method of allocation that does not take into account the equitable considerations referred to herein. The amount paid or payable by an indemnified party as a result of the loss, claim, damage or liability, or action in respect thereof, referred to above in this Section 7(d) shall be deemed to include, for purposes of this Section 7(d), any legal or other expenses reasonably incurred by such indemnified party in connection with investigating or defending any such action or claim. Notwithstanding the provisions of this Section 7(d), no Underwriter shall be required to contribute any amount in excess of the amount by which the net proceeds from the sale of the Notes underwritten by it exceeds the amount of any damages that such Underwriter has otherwise paid or become liable to pay by reason of any untrue or alleged untrue statement or omission or alleged omission. No person guilty of fraudulent misrepresentation (within the meaning of Section 11(f) of the Securities Act) shall be entitled to contribution from any person who was not guilty of such fraudulent misrepresentation. The Underwriters’ obligations to contribute as provided in this Section 7(d) are several in proportion to their respective underwriting obligations and not joint.

(e) The Underwriters severally confirm and each of the Partnership Parties acknowledges and agrees that the statements regarding delivery of Notes by the Underwriters set forth on the cover page of, the sentences related to concession and reallowance figures appearing under the caption “Underwriting—Commissions and Discounts,” the statements relating to the Underwriters’ intent to make a market in the Notes under the caption “Underwriting—New Issue of Notes” and the statements relating to stabilization by the Underwriters appearing under the caption “Underwriting—Price Stabilization, Short Positions and Penalty Bids” in, the most recent Preliminary Prospectus and the Prospectus are correct and constitute the only information concerning such Underwriters furnished in writing to the Partnership by or on behalf of the Underwriters specifically for inclusion in any Preliminary Prospectus, the Registration Statement, the Prospectus, any Issuer Free Writing Prospectus or in any amendment or supplement thereto or in any Marketing Materials.

8. Defaulting Underwriters . If, on the Delivery Date, any Underwriter defaults in the performance of its obligations under this Agreement, the remaining non-defaulting Underwriters shall be obligated to purchase the principal amount of the Notes that the defaulting Underwriter agreed but failed to purchase on the Delivery Date in the respective proportions which the principal amount of the Notes set forth opposite the name of each remaining non-defaulting Underwriter in Schedule I hereto bears to the aggregate principal

32

amount of Notes set forth opposite the names of all the remaining non-defaulting Underwriters in Schedule I hereto; provided, however , that the remaining non-defaulting Underwriters shall not be obligated to purchase any of the Notes on the Delivery Date if the aggregate principal amount of Notes that the defaulting Underwriter or Underwriters agreed but failed to purchase on such date exceeds 10% of the aggregate principal amount of Notes to be purchased on the Delivery Date, and any remaining non-defaulting Underwriter shall not be obligated to purchase more than 110% of the principal amount of the Notes that it agreed to purchase on the Delivery Date pursuant to the terms of Section 2. If the foregoing maximums are exceeded, the remaining non-defaulting Underwriters, or those other underwriters satisfactory to the Representatives who so agree, shall have the right, but shall not be obligated, to purchase, in such proportion as may be agreed upon among them, all the Notes to be purchased on the Delivery Date. If the remaining Underwriters or other underwriters satisfactory to the Representatives do not elect to purchase the Notes that the defaulting Underwriter or Underwriters agreed but failed to purchase on the Delivery Date, this Agreement shall terminate without liability on the part of any non-defaulting Underwriter or the Partnership Parties, except that the Partnership will continue to be liable for the payment of expenses to the extent set forth in Sections 5 and 10. As used in this Agreement, the term “Underwriter” includes, for all purposes of this Agreement unless the context requires otherwise, any party not listed in Schedule I hereto that, pursuant to this Section 8, purchases Notes that a defaulting Underwriter agreed but failed to purchase.

Nothing contained herein shall relieve a defaulting Underwriter of any liability it may have to the Partnership Parties for damages caused by its default. If other Underwriters are obligated or agree to purchase the Notes of a defaulting or withdrawing Underwriter, either the Representatives or the Partnership may postpone the Delivery Date for up to seven full business days in order to effect any changes that in the opinion of counsel for the Partnership or counsel for the Underwriters may be necessary in the Registration Statement, the Prospectus or in any other document or arrangement.

9. Termination . The obligations of the Underwriters hereunder may be terminated by the Representatives by notice given to and received by the Partnership prior to delivery of and payment for the Notes if, prior to that time, any of the events described in Sections 6(j), 6(k), 6(l) or 6(m) shall have occurred or if the Underwriters shall decline to purchase the Notes for any reason permitted under this Agreement.

10. Reimbursement of Underwriters’ Expenses . If the Partnership shall fail to tender the Notes for delivery to the Underwriters by reason of any failure, refusal or inability on the part of any Partnership Party to perform any agreement on their part to be performed, or because any other condition to the Underwriters’ obligations hereunder required to be fulfilled by the Partnership Parties is not fulfilled for any reason or (b) the Underwriters shall decline to purchase the Notes for any reason permitted under this Agreement, the Partnership will reimburse the Underwriters for all reasonable out-of-pocket expenses (including fees and disbursements of counsel) incurred by the Underwriters in connection with this Agreement and the proposed purchase of the Notes, and upon demand the Partnership shall pay the full amount thereof to the Representatives. If this Agreement is terminated pursuant to Section 8 by reason of the default of one or more Underwriters, the Partnership shall not be obligated to reimburse any defaulting Underwriter on account of those expenses.

33

11. Research Analyst Independence . The Partnership acknowledges that the Underwriters’ research analysts and research departments are required to be independent from their respective investment banking divisions and are subject to certain regulations and internal policies, and that such Underwriters’ research analysts may hold views and make statements or investment recommendations or publish research reports with respect to the Partnership and/or the offering that differ from the views of their respective investment banking divisions. The Partnership hereby waives and releases, to the fullest extent permitted by law, any claims that the Partnership may have against the Underwriters with respect to any conflict of interest that may arise from the fact that the views expressed by their independent research analysts and research departments may be different from or inconsistent with the views or advice communicated to the Partnership by such Underwriters’ investment banking divisions. The Partnership acknowledges that each of the Underwriters is a full service securities firm and as such from time to time, subject to applicable securities laws, may effect transactions for its own account or the account of its customers and hold long or short positions in debt or equity securities of the companies that may be the subject of the transactions contemplated by this Agreement.

12. No Fiduciary Duty . The Partnership Parties acknowledge and agree that in connection with this offering, sale of the Notes or any other services the Underwriters may be deemed to be providing hereunder, notwithstanding any preexisting relationship, advisory or otherwise, between the parties or any oral representations or assurances previously or subsequently made by the Underwriters: (i) no fiduciary or agency relationship between the Partnership Parties and any other person, on the one hand, and the Underwriters, on the other hand, exists; (ii) the Underwriters are not acting as advisors, expert or otherwise, to any of the Partnership Parties, including, without limitation, with respect to the determination of the public offering price of the Notes, and such relationship between the Partnership Parties, on the one hand, and the Underwriters, on the other hand, is entirely and solely commercial, based on arms-length negotiations; (iii) any duties and obligations that the Underwriters may have to the Partnership Parties shall be limited to those duties and obligations specifically stated herein; and (iv) the Underwriters and their respective affiliates may have interests that differ from those of the Partnership Parties. The Partnership Parties hereby waive any claims that the Partnership Parties may have against the Underwriters with respect to any breach of fiduciary duty in connection with this offering of Securities.

13. Notices, Etc . All statements, requests, notices and agreements hereunder shall be in writing, and:

(a) if to the Underwriters, shall be delivered or sent by mail or facsimile transmission to Barclays Capital Inc., 200 Park Avenue, New York, New York 10166, Attention: High Grade Syndicate (Fax: 212-412-7305) or J.P. Morgan Securities Inc., 270 Park Avenue, New York, NY 10017 Attn: High Grade Syndicate (Fax: 212-834-6081); and

(b) if to any of the Partnership Parties, shall be delivered or sent by mail or facsimile transmission to NuStar Energy L.P., 2330 N. Loop 1604 West, San Antonio, Texas 78248, Attention: Bradley C. Barron, Senior Vice President, General Counsel and Secretary (Fax: 210-918-5500).

34

Any such statements, requests, notices or agreements shall take effect at the time of receipt thereof. The Partnership Parties shall be entitled to act and rely upon any request, consent, notice or agreement given or made on behalf of the Underwriters by Barclays Capital Inc.

14. Persons Entitled to Benefit of Agreement . This Agreement shall inure to the benefit of and be binding upon the Underwriters, the Partnership Parties and their respective successors. This Agreement and the terms and provisions hereof are for the sole benefit of only those persons, except that (A) the representations, warranties, indemnities and agreements of the Partnership Parties contained in this Agreement shall also be deemed to be for the benefit of the directors, officers and employees of the Underwriters and each person or persons, if any, who control any Underwriter within the meaning of Section 15 of the Securities Act and (B) the indemnity agreement of the Underwriters contained in Section 7(b) of this Agreement shall be deemed to be for the benefit of the directors and managers of the Partnership, the officers of the Partnership who have signed the Registration Statement and any person controlling the Partnership within the meaning of Section 15 of the Securities Act. Nothing in this Agreement is intended or shall be construed to give any person, other than the persons referred to in this Section 14, any legal or equitable right, remedy or claim under or in respect of this Agreement or any provision contained herein.

15. Survival . The respective indemnities, representations, warranties and agreements of the Partnership Parties and the Underwriters contained in this Agreement or made by or on behalf of them, respectively, pursuant to this Agreement, shall survive the delivery of and payment for the Notes and shall remain in full force and effect, regardless of any investigation made by or on behalf of any of them or any person controlling any of them.

16. Definition of the Terms “Business Day” and “Subsidiary .” For purposes of this Agreement, (a) “ business day ” means each Monday, Tuesday, Wednesday, Thursday or Friday that is not a day on which banking institutions in New York are generally authorized or obligated by law or executive order to close and (b) “ subsidiary ” has the meaning set forth in Rule 405.

17. Governing Law . This Agreement shall be governed by and construed in accordance with the laws of the State of New York .

18. Counterparts . This Agreement may be executed in one or more counterparts and, if executed in more than one counterpart, the executed counterparts shall each be deemed to be an original but all such counterparts shall together constitute one and the same instrument.

19. Headings . The headings herein are inserted for convenience of reference only and are not intended to be part of, or to affect the meaning or interpretation of, this Agreement.

35

If the foregoing correctly sets forth the agreement among the Partnership Parties and the Underwriters, please indicate your acceptance in the space provided for that purpose below.

36

37

38

Schedule II

SCHEDULE III

Issuer Free Writing Prospectuses Included in Disclosure Package

None, other than the Final Term Sheet attached as Schedule IV.

Note: A securities rating is not a recommendation to buy, sell, or hold securities and may be subject to review, revision, suspension, reduction, or withdrawal at any time by the assigning rating agency.

The issuer has filed a registration statement (including a prospectus) with the SEC for the offering to which this communication relates. Before you invest, you should read the prospectus in that registration statement and other documents the issuer has filed with the SEC for more complete information about the issuer and this offering. You may get these documents for free by visiting EDGAR on the SEC Web site at www.sec.gov. Alternatively, the issuer, any underwriter or any dealer participating in the offering will arrange to send you the prospectus if you request it by calling Barclays Capital Inc. at toll free 1-888-227-2775, Ext. 2663, by calling J.P. Morgan Securities Inc. collect at 1-212-834-4533, or by calling SunTrust Robinson Humphrey, Inc. toll free at (800) 685-4786.

Schedule IV

EXHIBIT A-1

FORM OF OPINION OF ANDREWS KURTH LLP

1. Formation, Valid Existence and Good Standing . Each of Riverwalk Holdings, NuStar GP, the General Partner, the Partnership, NuStar Logistics and GP, Inc. has been duly formed, is validly existing and in good standing as a limited partnership, limited liability company or corporation, as applicable, under the laws of the State of Delaware. Each of the NuStar OLP Entities is validly existing and in good standing as a limited partnership or limited liability company, as applicable, under the laws of the State of Delaware.

2. Power and Authority. Each of Riverwalk Holdings, NuStar GP, the General Partner, the Partnership, NuStar Logistics, GP, Inc. and the NuStar OLP Entities has the limited partnership, limited liability company or corporate power and authority, as the case may be, necessary to (i) execute and deliver, and incur and perform all of its obligations under, the Transaction Documents to which it is a party and (ii) carry on its business and own or lease its properties as described in the most recent Preliminary Prospectus and the Prospectus. For the purposes of this Exhibit A-1, “Transaction Documents” means, collectively, the Underwriting Agreement, the Indenture, the Notes and the Guarantee.

3. Ownership of Riverwalk Holdings by NuStar Holdings . NuStar Holdings is the sole member of Riverwalk Holdings and owns 100% of the issued and outstanding membership interests in Riverwalk Holdings; such membership interests have been duly authorized and validly issued in accordance with the Riverwalk Holdings LLC Agreement and are fully paid (to the extent required under the Riverwalk Holdings LLC Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Sections 18-303 and 18-607 of the Delaware LLC Act); and NuStar Holdings owns such membership interests free and clear of all liens, encumbrances, security interests, charges or claims (i) in respect of which a financing statement under the Uniform Commercial Code of the State of Delaware naming NuStar Holdings as debtor is on file as of a recent date in the office of the Secretary of State of the State of Delaware or (ii) otherwise known to such counsel, without independent investigation, other than those created by or arising under Sections 18-303 and 18-607 of the Delaware LLC Act or contained in the Riverwalk Holdings LLC Agreement.

4. Ownership of NuStar GP by NuStar Holdings. At the Delivery Date, NuStar Holdings is the sole member of NuStar GP and owns 100% of the issued and outstanding membership interests in NuStar GP; such membership interests have been duly authorized and validly issued in accordance with the NuStar GP LLC Agreement and are fully paid (to the extent required under the NuStar GP LLC Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Sections 18-303 and 18-607 of the Delaware LLC Act); and NuStar Holdings owns such membership interests free and clear of all liens, encumbrances, security interests, charges or claims (i) in respect of which a financing statement under the Uniform Commercial Code of the State of Delaware naming NuStar Holdings as debtor is on file as of a recent date in the office of the Secretary of State of the State of Delaware or (ii) otherwise known to such counsel, without independent investigation, other than those created by or arising under Sections 18-303 and 18-607 of the Delaware LLC Act or contained in the NuStar GP LLC Agreement.

1

5. Ownership of the General Partner Interests in the General Partner . NuStar GP is the sole general partner of the General Partner with a 0.1% general partner interest in the General Partner; such general partner interest has been duly authorized and validly issued in accordance with the GP Partnership Agreement; and NuStar GP owns such general partner interest free and clear of all liens, encumbrances, security interests, charges or claims (i) in respect of which a financing statement under the Uniform Commercial Code of the State of Delaware naming NuStar GP as debtor is on file as of a recent date in the office of the Secretary of State of the State of Delaware or (ii) otherwise known to such counsel, without independent investigation, other than those created by or arising under Sections 17-303(a) and 17-607 of the Delaware LP Act or contained in the GP Partnership Agreement.

6. Ownership of the Limited Partner Interests in the General Partner . Riverwalk Holdings is the sole limited partner of the General Partner with a 99.9% limited partner interest in the General Partner; such limited partner interest has been duly authorized and validly issued in accordance with the GP Partnership Agreement and is fully paid (to the extent required under the GP Partnership Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Sections 17-303 and 17-607 of the Delaware LP Act); and Riverwalk Holdings owns such limited partner interest free and clear of all liens, encumbrances, security interests, charges or claims (i) in respect of which a financing statement under the Uniform Commercial Code of the State of Delaware naming Riverwalk Holdings as debtor is on file as of a recent date in the office of the Secretary of State of the State of Delaware or (ii) otherwise known to such counsel, without independent investigation, other than those created by or arising under Sections 17-303(a) and 17-607 of the Delaware LP Act or contained in the GP Partnership Agreement.

7. Ownership of the General Partner Interest and Incentive Distribution Rights in the Partnership . The General Partner is the sole general partner of the Partnership with a 2% general partner interest and 100% of the Incentive Distribution Rights in the Partnership; such general partner interest and Incentive Distribution Rights have been duly authorized and validly issued in accordance with the Partnership Agreement and, in the case of the Incentive Distribution Rights, are fully paid (to the extent required under the Partnership Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Sections 17-303 and 17-607 of the Delaware LP Act); and the General Partner owns such general partner interest and Incentive Distribution Rights, in each case, free and clear of all liens, encumbrances, security interests, charges or claims (i) in respect of which a financing statement under the Uniform Commercial Code of the State of Delaware naming the General Partner as debtor is on file as of a recent date in the office of the Secretary of State of the State of Delaware or (ii) otherwise known to such counsel, without independent investigation, other than those created by or arising under Sections 17-303(a) and 17-607 of the Delaware LP Act or contained in the Partnership Agreement.

8. Ownership of the Partnership’s Common Units by NuStar Holdings . Riverwalk Holdings and NuStar GP own 10,213,894 and 6,416 of the Partnership’s common units, respectively, in the Partnership; such limited partner interests have been duly authorized and validly issued in accordance with the Partnership Agreement and are fully paid (to the extent required under the Partnership Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Sections 17-303 and 17-607 of the Delaware LP Act);

2

and Riverwalk Holdings and NuStar GP own such limited partner interests free and clear of all liens, encumbrances, security interests, charges or claims (i) in respect of which a financing statement under the Uniform Commercial Code of the State of Delaware naming Riverwalk Holdings and/or NuStar GP as debtor is on file as of a recent date in the office of the Secretary of State of the State of Delaware or (ii) otherwise known to such counsel, without independent investigation, other than those created by or arising under Sections 17-303(a) and 17-607 of the Delaware LP Act or contained in the Partnership Agreement.

9. Ownership of GP, Inc. by the Partnership . The Partnership owns 100% of the issued and outstanding capital stock of GP, Inc.; such shares of capital stock have been duly authorized and validly issued in accordance with the certificate of incorporation and bylaws of GP, Inc., as amended to date, and are fully paid and nonassessable; and the Partnership owns such shares of capital stock free and clear of all liens, encumbrances, security interests, charges or claims (i) in respect of which a financing statement under the Uniform Commercial Code of the State of Delaware naming the Partnership as debtor is on file as of a recent date in the office of the Secretary of State of the State of Delaware or (ii) otherwise known to such counsel, without independent investigation.

10. Ownership of the General Partner Interest in NuStar Logistics . GP, Inc. is the sole general partner of NuStar Logistics with a 0.01% general partner interest in NuStar Logistics; such general partner interest has been duly authorized and validly issued in accordance with the NuStar Logistics Partnership Agreement; and GP, Inc. owns such general partner interest free and clear of all liens, encumbrances, security interests, charges or claims (i) in respect of which a financing statement under the Uniform Commercial Code of the State of Delaware naming GP, Inc. as debtor is on file as of a recent date in the office of the Secretary of State of the State of Delaware or (ii) otherwise known to such counsel, without independent investigation, other than those created by or arising under Sections 17-303(a) and 17-607 of the Delaware LP Act or contained in the NuStar Logistics Partnership Agreement.

11. Ownership of the Limited Partner Interest in NuStar Logistics . The Partnership is the sole limited partner of NuStar Logistics with a 99.99% limited partner interest in NuStar Logistics; such limited partner interest has been duly authorized and validly issued in accordance with the NuStar Logistics Partnership Agreement and is fully paid (to the extent required under the NuStar Logistics Partnership Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Sections 17-303 and 17-607 of the Delaware LP Act); and the Partnership owns such limited partner interest free and clear of all liens, encumbrances, security interests, charges or claims (i) in respect of which a financing statement under the Uniform Commercial Code of the State of Delaware naming the Partnership as debtor is on file as of a recent date in the office of the Secretary of State of the State of Delaware or (ii) otherwise known to such counsel, without independent investigation, other than those created by or arising under Sections 17-303(a) and 17-607 of the Delaware LP Act or contained in the NuStar Logistics Partnership Agreement.

12. Ownership of LegacyStar Services by the Partnership . The Partnership is the sole member of LegacyStar Services and owns 100% of the issued and outstanding membership interests in LegacyStar Services; such membership interests have been duly authorized and validly issued in accordance with the LegacyStar Services LLC Agreement and are fully paid (to

3

the extent required under the LegacyStar Services LLC Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Sections 18-303 and 18-607 of the Delaware LLC Act); and the Partnership owns such membership interests free and clear of all liens, encumbrances, security interests, charges or claims (i) in respect of which a financing statement under the Uniform Commercial Code of the State of Delaware naming the Partnership as debtor is on file as of a recent date in the office of the Secretary of State of the State of Delaware or (ii) otherwise known to such counsel, without independent investigation, other than those created by or arising under Sections 18-303 and 18-607 of the Delaware LLC Act.

13. Ownership of NuStar Pipeline GP . LegacyStar Services is the sole member of NuStar Pipeline GP and owns 100% of the issued and outstanding membership interests in NuStar Pipeline GP; such membership interests have been duly authorized and validly issued in accordance with the NuStar Pipeline GP LLC Agreement and are fully paid (to the extent required under the NuStar Pipeline GP LLC Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Sections 18-303 and 18-607 of the Delaware LLC Act); and LegacyStar Services owns such membership interests free and clear of all liens, encumbrances, security interests, charges or claims (i) in respect of which a financing statement under the Uniform Commercial Code of the State of Delaware naming LegacyStar Services as debtor is on file as of a recent date in the office of the Secretary of State of the State of Delaware or (ii) otherwise known to such counsel, without independent investigation, other than those created by or arising under Sections 18-303 and 18-607 of the Delaware LLC Act.

14. Ownership of the General Partner Interest in NPP . NuStar Pipeline GP is the sole general partner of NPP with a 1% general partner interest in NPP; such general partner interest has been duly authorized and validly issued in accordance with the NPP Partnership Agreement; and NuStar Pipeline GP owns such general partner interest free and clear of all liens, encumbrances, security interests, charges or claims (i) in respect of which a financing statement under the Uniform Commercial Code of the State of Delaware naming NuStar Pipeline GP as debtor is on file as of a recent date in the office of the Secretary of State of the State of Delaware or (ii) otherwise known to such counsel, without independent investigation, other than those created by or arising under Sections 17-303(a) and 17-607 of the Delaware LP Act or contained in the NPP Partnership Agreement.

15. Ownership of the Limited Partner Interest in NPP . The Partnership is the sole limited partner of NPP with a 99% limited partner interest in NPP; such limited partner interest has been duly authorized and validly issued in accordance with the NPP Partnership Agreement and is fully paid (to the extent required under the NPP Partnership Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Sections 17-303 and 17-607 of the Delaware LP Act); and the Partnership owns such limited partner interest free and clear of all liens, encumbrances, security interests, charges or claims (i) in respect of which a financing statement under the Uniform Commercial Code of the State of Delaware naming the Partnership as debtor is on file as of a recent date in the office of the Secretary of State of the State of Delaware or (ii) otherwise known to such counsel, without independent investigation, other than those created by or arising under Sections 17-303(a) and 17-607 of the Delaware LP Act or contained in the NPP Partnership Agreement.

4

16. Ownership of the General Partner Interest in NPOP . NuStar Pipeline GP is the sole general partner of NPOP with a 1% general partner interest in NPOP; such general partner interest has been duly authorized and validly issued in accordance with the NPOP Partnership Agreement; and NuStar Pipeline GP owns such general partner interest free and clear of all liens, encumbrances, security interests, charges or claims (i) in respect of which a financing statement under the Uniform Commercial Code of the State of Delaware naming NuStar Pipeline GP as debtor is on file as of a recent date in the office of the Secretary of State of the State of Delaware or (ii) otherwise known to such counsel, without independent investigation, other than those created by or arising under Sections 17-303(a) and 17-607 of the Delaware LP Act or contained in the NPOP Partnership Agreement.

17. Ownership of the Limited Partner Interest in NPOP . NPP is the sole limited partner of NPOP with a 99% limited partner interest in NPOP; such limited partner interest has been duly authorized and validly issued in accordance with the NPOP Partnership Agreement and is fully paid (to the extent required under the NPOP Partnership Agreement) and nonassessable (except as such nonassessability may be affected by matters described in Sections 17-303 and 17-607 of the Delaware LP Act); and NPP owns such limited partner interest free and clear of all liens, encumbrances, security interests, charges or claims (i) in respect of which a financing statement under the Uniform Commercial Code of the State of Delaware naming NPP as debtor is on file as of a recent date in the office of the Secretary of State of the State of Delaware or (ii) otherwise known to such counsel, without independent investigation, other than those created by or arising under Sections 17-303(a) and 17-607 of the Delaware LP Act or contained in the NPOP Partnership Agreement.

18. No Registration Rights or Options . To such counsel’s knowledge, neither the filing of the Registration Statement nor the offering or sale of the Securities as contemplated by the Underwriting Agreement gives rise to any rights for or relating to the registration of any securities of the Partnership other than rights which have been waived.

19. Authorization, Execution and Delivery . (a) Each of the Underwriting Agreement, the Base Indenture, the Supplemental Indenture and the Notes has been duly authorized, executed and delivered by NuStar Logistics. (b) Each of the Underwriting Agreement, the Base Indenture, the Supplemental Indenture and the Guarantee has been duly authorized, executed and delivered by the Partnership. (c) Each of the Underwriting Agreement, the Supplemental Indenture and the Guarantee has been duly authorized, executed and delivered by NPOP. (d) The Underwriting Agreement has been duly authorized, executed and delivered by each of GP, Inc., the General Partner, NuStar GP and NuStar Pipeline GP.

20. Authorization, Execution, Delivery and Enforceability of Certain Partnership Entities Agreements . The NuStar GP LLC Agreement, the Riverwalk Holdings LLC Agreement, the GP Partnership Agreement, the Partnership Agreement, the NuStar Logistics Partnership Agreement and the NPOP Partnership Agreement have been duly authorized, executed and delivered by the Partnership and the Partnership Entities thereto, as applicable. Each of the Organizational Documents is a valid and legally binding agreement of the parties thereto, enforceable against such parties in accordance with their terms.

5

21. Enforceability of the Indenture. The Indenture has been duly qualified under the Trust Indenture Act and constitutes a valid and legally binding obligation of each of NuStar Logistics, the Partnership and NPOP, enforceable against each of them in accordance with its terms, under the laws of the State of New York.

22. Enforceability of the Notes . When authenticated by the Trustee in the manner provided in the Indenture and delivered to and paid for by the Underwriters in accordance with the Underwriting Agreement, the Notes will constitute valid and legally binding obligations of NuStar Logistics, entitled to the benefits of the Indenture and enforceable against NuStar Logistics in accordance with their terms, under the laws of the State of New York.

23. Enforceability of the Guarantee . When the Notes have been authenticated by the Trustee in the manner provided in the Indenture and delivered to and paid for by the Underwriters in accordance with the Underwriting Agreement, the Guarantee included in the Indenture will constitute a valid and legally binding obligation of the Partnership and NPOP, enforceable against each of them in accordance with the terms of the Indenture, under the laws of the State of New York.

24. No Violation . None of (i) the execution and delivery of, or the incurrence or performance by each of the Partnership Parties of its obligations under, each of the Transaction Documents to which it is a party, each in accordance with its terms, (ii) the offering, issuance, sale and delivery of the Notes pursuant to the Underwriting Agreement or (iii) the issuance of the Guarantee by the Partnership and NPOP, (A) constituted, constitutes or will constitute a violation of the Organizational Documents, (B) constituted, constitutes or will constitute a breach or violation of, or a default (or an event which, with notice or lapse of time or both, would constitute such a default), under any Applicable Agreement, (C) resulted, results or will result in the creation of any security interest in, or lien upon, any of the property or assets of any of the Partnership Entities pursuant to any Applicable Agreement, (D) resulted, results or will result in any violation of (i) applicable laws of the State of New York, (ii) applicable laws of the State of Texas, (iii) applicable laws of the United States of America, (iv) the Delaware LP Act, (v) the DGCL, (vi) the Delaware LLC Act or (vii) Regulation T, U or X of the Board of Governors of the Federal Reserve System, or (E) resulted, results or will result in the contravention of any Applicable Order.

For the purposes of this Exhibit A-1, (a) “Applicable Agreements” means, collectively, those agreements and other instruments identified on a schedule attached to an officers’ certificate attached hereto, which shall be certified by officers of GP, Inc., NuStar GP and NuStar Pipeline GP as being every indenture, mortgage, deed of trust, loan, purchase or credit agreement, lease or other agreement that is material in relation to the business, operations, affairs, financial condition, assets, or properties of the Partnership Parties and their respective subsidiaries, considered as a single enterprise, and (b) “Applicable Orders” means, collectively, those orders or decrees of governmental authorities identified on a schedule attached to an officers’ certificate attached hereto, which shall be been certified by officers of GP, Inc., NuStar GP and NuStar Pipeline GP as being every order or decree of any governmental authority by which any of the Partnership Parties or any of its subsidiaries or any of their respective properties is bound, that is material in relation to the business, operations, affairs, financial condition, assets, or properties of the Partnership Parties and their respective subsidiaries, considered as a single enterprise.

6

25. No Consents . No Governmental Approval, which has not been obtained or taken and is not in full force and effect, is required to authorize, or is required for the execution and delivery by each of the Partnership Parties of, the Transaction Documents to which it is a party or the incurrence or performance of its obligations thereunder, or the enforceability of any of such Transaction Documents against any of the Partnership Parties that is a party thereto. As used in this paragraph, “Governmental Approval” means any consent, approval, license, authorization or validation of, or filing, recording or registration with, any executive, legislative, judicial, administrative or regulatory body of the State of New York, the State of Texas, the State of Delaware or the United States of America, pursuant to (i) applicable laws of the State of New York, (ii) applicable laws of the State of Texas, (iii) applicable laws of the United States of America, (iv) the Delaware LP Act, (v) the DGCL or (vi) the Delaware LLC Act.

26. Description of the Notes . The statements under the caption “Description of NuStar Logistics Debt Securities” in the Base Prospectus and “Description of the Notes” in the Pricing Disclosure Package and the Prospectus, insofar as such statements purport to summarize certain provisions of documents referred to therein and reviewed by us as described above, fairly summarize such provisions in all material respects, subject to the qualifications and assumptions stated therein.

27. Tax Matters . The statements in the most recent Preliminary Prospectus and the Prospectus under the caption “Material U.S. Federal Income Tax Considerations,” insofar as they refer to statements of law or legal conclusions, fairly summarize the matters referred to therein in all material respects, subject to the qualifications and assumptions stated therein.

28. Investment Company . None of the Partnership Entities is and, after giving effect to the offer and sale of the Securities and the application of the proceeds therefrom as described under “Use of Proceeds” in the Prospectus, none of them will be an “investment company” within the meaning of such term under the Investment Company Act of 1940, as amended.

29. Filing of the Prospectus. Any required filing of the most recent Preliminary Prospectus and the Prospectus pursuant to Rule 424(b) under the Securities Act and of any Issuer Free Writing Prospectus pursuant to Rule 433 under the Securities Act has been made in the manner and within the time periods required by such rule.

In rendering such opinion, such counsel may (i) rely in respect of matters of fact upon certificates of officers and employees of the Partnership and upon information obtained from public officials, (ii) assume that all documents submitted to them as originals are authentic, that all copies submitted to them conform to the originals thereof, and that the signatures on all documents examined by them are genuine, (iii) state that its opinion is limited to matters governed by the federal laws of the United States of America and the Delaware LP Act, the Delaware LLC Act, the DGCL, Texas law and New York law and (iv) state that they express no opinion with respect to state or local taxes or tax statutes to which any of the members or limited partners of any of the Partnership Entities may be subject.

7

In addition, such counsel shall state that they have participated in conferences with officers and other representatives of the Partnership Parties, the independent registered public accounting firm for NuStar Logistics, the Partnership and NPOP, such entities’ counsel and representatives at which the contents of the Registration Statement, the Pricing Disclosure Package and the Prospectus (including the Incorporated Documents) and related matters were discussed and, although such counsel has not independently verified and is not passing upon, and does not assume any responsibility for, the accuracy, completeness or fairness of the statements contained or incorporated by reference in the Registration Statement, the Pricing Disclosure Package and the Prospectus (except as and to the extent set forth in paragraphs 26 and 27 above), on the basis of the foregoing (relying with respect to factual matters to the extent such counsel deems appropriate upon statements by officers and other representatives of the Partnership Parties), (a) such counsel confirms to the Underwriters that, in its opinion, each of the Registration Statement, as of its latest Effective Date, the Preliminary Prospectus, as of its date, and the Prospectus, as of its date, appeared on its face to be appropriately responsive in all material respects to the requirements of the Securities Act and the Rules and Regulations (except that such counsel expresses no statement or belief as to Regulation S-T), (b) such counsel has not become aware of any documents that are required to be filed as exhibits to the Registration Statement or any of the Incorporated Documents and are not so filed or of any documents that are required to be summarized in the Preliminary Prospectus or the Prospectus or any of the Incorporated Documents, and are not so summarized and (c) furthermore, no facts have come to such counsel’s attention that have led such counsel to believe that (i) the Registration Statement, as of its latest Effective Date, contained an untrue statement of a material fact or omitted to state any material fact required to be stated therein or necessary to make the statements therein not misleading, (ii) the Pricing Disclosure Package (including the Incorporated Documents), as of the Applicable Time, contained any untrue statement of a material fact or omitted to state any material fact necessary to make the statements therein, in light of the circumstances under which they were made, not misleading, or (iii) the Prospectus (including the Incorporated Documents), as of its date and as of the date hereof, contained or contains an untrue statement of a material fact or omitted or omits to state any material fact necessary to make the statements therein, in light of the circumstances under which they were made, not misleading, it being understood that such counsel expresses no opinion, statement or belief in this letter with respect to (i) the historical financial statements and related schedules, including the notes and schedules thereto and the auditor’s report thereon, (ii) any other financial or accounting data, included or incorporated or deemed incorporated by reference in, or excluded from, the Registration Statement or the Prospectus or the Pricing Disclosure Package and (iii) the Form T-1 included as an exhibit to the Registration Statement and representations and warranties and other statements of fact included in the exhibits to the Registration Statement or Incorporated Documents.

For the purposes of this Exhibit A-1, “Incorporated Documents” means each of NuStar Logistics’, the Partnership’s or NPOP’s reports that have been filed with the Commission and are incorporated by reference in the Registration Statement.

Furthermore, such counsel has been orally advised by the Commission that no stop order suspending the effectiveness of the Registration Statement has been issued. To such counsel’s knowledge based solely upon such oral communication with the Commission, no proceedings for that purpose have been instituted or are pending or threatened by the Commission.

8

EXHIBIT A-2

FORM OF OPINION OF BRADLEY C. BARRON

1. Formation and Qualification . Each of the Operating Subsidiaries is validly existing and in good standing as a limited partnership, limited liability company or corporation, as applicable, under the laws of its jurisdiction of organization, as set forth opposite its name on Annex 1 to this opinion, with full partnership, limited liability company or corporate power and authority, as the case may be, necessary to own or lease its properties currently owned or leased or to be owned or leased at the Delivery Date, if any, and to conduct its business as currently conducted or to be conducted at the Delivery Date, in each case in all material respects as described in the most recent Preliminary Prospectus and the Prospectus. Each of the entities listed on Annex 2 to this opinion is duly qualified or registered to do business and is in good standing as a foreign limited partnership, limited liability company or corporation, as applicable, in each jurisdiction set forth opposite its name on Annex 2 to this opinion.

2. Ownership of the Operating Subsidiaries . Except as set forth on Annex 1 to this opinion, each of NuStar Logistics and NPOP, as applicable, own 100% of the outstanding capital stock, membership interests or partnership interests, as the case may be, in each of the Operating Subsidiaries; the membership interests or partnership interests of NTOP, Shore Terminals and NuStar Asphalt have been duly authorized and validly issued in accordance with the applicable Operating Subsidiaries Operative Documents and, except in the case of the general partner interests, are fully paid (to the extent required under the applicable Operating Subsidiary Operative Document) and nonassessable (except as such nonassessability may be affected by Sections 18-303 and 18-607 of the Delaware LLC Act or Sections 17-303(a) and 17-607 of the Delaware LP Act, as the case may be); and each of NuStar Logistics and NPOP, as applicable, own all such stock, membership interests or partnership interests, as the case may be, free and clear of all liens, encumbrances, security interests, charges or claims (i) in respect of which a financing statement under the Uniform Commercial Code of the State of Delaware naming any of NuStar Logistics or NPOP as debtor is on file as of a recent date in the office of the Secretary of State of the State of Delaware or (ii) otherwise known to such counsel, without independent investigation, other than those created by or arising under the Delaware LLC Act or Delaware LP Act, as the case may be.

3. No Preemptive Rights . Except as identified in the most recent Preliminary Prospectus and the Prospectus, there are no preemptive rights or other rights to subscribe for or to purchase, nor any restriction upon the voting or transfer of any equity securities of the Partnership pursuant to any agreement or instrument known to such counsel to which the Partnership is a party or is subject. To such counsel’s knowledge, except as described in the most recent Preliminary Prospectus and the Prospectus, there are no outstanding options, warrants or other rights to purchase or exchange any securities of the Partnership.

4. No Violation . None of the (i) offering or sale by NuStar Logistics of the Notes, (ii) the issuance by the Partnership and NPOP of the Guarantee, (iii) the execution, delivery and performance of the Underwriting Agreement, the Organizational Documents and the Indenture by the Partnership Entities that are parties thereto, or (iv) the consummation of any other transactions contemplated by the Underwriting Agreement, the Organizational Documents,

1

or the Indenture or the fulfillment of the terms hereof or thereof, will result in a breach or violation of, or a default (or an event that, with notice or lapse of time or both, would constitute such a default) under, or result in a change of control under, or imposition of any lien, charge or encumbrance upon any property or assets of any of the Partnership Entities pursuant to (A)   any agreement, lease or other instrument known to such counsel to which any of the Partnership Entities is a party or by which any of them or their properties is subject, (other than any of the Organizational Documents or any other agreement filed as an exhibit to the Registration Statement, to which such counsel is not opining), or (B) to such counsel’s knowledge, any judgment, order, decree, injunction, rule or regulation of any court, arbitrator or governmental agency or body having jurisdiction over any of the Partnership Entities or any of their assets or properties, which breaches, violations, defaults or liens would reasonably be expected to have a Material Adverse Effect, or could materially impair the ability of any of the Partnership Entities to perform their obligations under the Underwriting Agreement, the Organizational Documents or the Indenture.

5. Permits. To the knowledge of such counsel, each of the Partnership Entities has such Permits as are necessary under applicable law to own their properties and conduct their businesses in the manner described in the most recent Preliminary Prospectus and the Prospectus, except for any of the foregoing that would not, in the aggregate, reasonably be expected to have a Material Adverse Effect; each of the Partnership Entities has fulfilled and performed all of its obligations with respect to the Permits, and no event has occurred that allows, or after notice or lapse of time would allow, revocation or termination thereof or results in any other impairment of the rights of the holder or any such Permits, except for any of the foregoing that would not reasonably be expected to have a Material Adverse Effect.

In rendering such opinion, such counsel may (i) rely in respect of matters of fact upon representations of the Partnership Parties set forth in the Underwriting Agreement and upon certificates of officers and employees of the Partnership Parties and upon information obtained from public officials, (ii) assume that all documents submitted to them as originals are authentic, that all copies submitted to them conform to the originals thereof, and that the signatures on all documents examined by them are genuine, (iii) state that its opinion is limited to matters governed by the federal laws of the United States of America and the Delaware LP Act, the Delaware LLC Act, the DGCL and Texas law.

In addition, such counsel shall state that they have participated in conferences with officers and other representatives of the Partnership, the independent registered public accounting firm of the Partnership, your counsel and your representatives at which the contents of the Registration Statement, the Pricing Disclosure Package and the Prospectus and related matters were discussed and, although such counsel has not independently verified and is not passing upon, and does not assume any responsibility for, the accuracy, completeness or fairness of the statements contained in the Registration Statement, the Pricing Disclosure Package and the Prospectus, on the basis of the foregoing, no facts have come to such counsel’s attention that lead such counsel to believe that:

(A) the Registration Statement, as of the latest Effective Time, contained an untrue statement of a material fact or omitted to state any material fact required to be stated therein or necessary to make the statements therein not misleading;

2

(B) the Pricing Disclosure Package, as of the Applicable Time, contained any untrue statement of a material fact or omitted to state any material fact necessary to make the statements therein, in light of the circumstances under which they were made, not misleading; or

(C) the Prospectus, as of its date and as of the date hereof, contained or contains an untrue statement of a material fact or omitted or omits to state any material fact necessary to make the statements therein, in the light of the circumstances under which they were made, not misleading;

it being understood that such counsel expresses no opinion, statement or belief in this letter with respect to (i) the financial statements and related schedules, including the notes and schedules thereto and the auditor’s report thereon, (ii) any other financial or accounting data, included in, or excluded from, the Registration Statement or the Prospectus or the Pricing Disclosure Package, and (iii) representations and warranties and other statements of fact included in the exhibits to the Registration Statement.

3