SERVICES AGREEMENT

Exhibit 10.01

SERVICES AGREEMENT

This Services Agreement (this “Agreement”), effective as of January 1, 2008 (the “Effective Date”), is entered into by and between NUSTAR ENERGY L.P., a Delaware limited partnership (“NuStar Energy”) and NUSTAR GP, LLC, a Delaware limited liability company (“GP, LLC”) and a wholly owned subsidiary of NuStar GP Holdings, LLC, a Delaware limited liability company (“Holdings”).

RECITALS

WHEREAS, in accordance with Section 7.1 of the Third Amended and Restated Agreement of Limited Partnership of NuStar Energy (the “Partnership Agreement”), GP, LLC provides all executive management, accounting, legal, cash management, corporate finance and other administrative services necessary and appropriate, in its sole discretion, to conduct the business of NuStar Energy;

WHEREAS, Section 7.4(b) of the Partnership Agreement provides that GP, LLC shall be reimbursed on a monthly basis, or such other reasonable basis as GP, LLC may determine in its sole discretion, for (i) all direct and indirect expenses it incurs or payments it makes on behalf of NuStar Energy and (ii) all other necessary or appropriate expenses allocable to NuStar Energy or otherwise reasonably incurred by GP, LLC in connection with operating NuStar Energy’s business;

WHEREAS, GP, LLC also provides the administrative services necessary to conduct the business of Holdings;

WHEREAS, GP, LLC and NuStar Energy desire to enter into this Agreement to determine the allocation of reimbursements due GP, LLC for services provided by GP, LLC to each of Holdings and NuStar Energy;

WHEREAS, on April 24, 2008, the independent directors of GP, LLC approved the terms of this Agreement; and

NOW, THEREFORE, for and in consideration of the mutual covenants contained in this Agreement, the parties hereto agree as follows:

ARTICLE I

DEFINITIONS

Section 1.1 Definitions. The following definitions shall be for all purposes, unless otherwise clearly indicated to the contrary, applied to the terms used in this Agreement.

(a) “Affiliates” means entities that directly or indirectly through one or more intermediaries control, or are controlled by, or are under common control with, such party, and the term “control” shall mean the possession, directly or indirectly, of the power to direct or cause the direction of management and policies of an entity, whether through the ownership of voting securities, by contract or otherwise.

(b) “force majeure” means any one or more of: (a) an act of God, (b) a strike, lockout, labor difficulty or other industrial disturbance, (c) an act of a public enemy, war, blockade, insurrection or public riot, (d) lightning, fire, storm, flood or explosion, (e) governmental action, delay, restraint or inaction, (f) judicial order or injunction, (g) material shortage or unavailability of equipment, or (h) any other cause or event, whether of the kind specifically enumerated above or otherwise, which is not reasonably within the control of the party claiming suspension.

(c) “Holdings Administrative Services Fee” means (i) for fiscal year 2008, $750,000, plus 1.0% of GP, LLC’s domestic bonus and unit compensation expense and (ii) for fiscal year 2009 and each fiscal year thereafter, $1.1 million (as adjusted pursuant to Section 2.2(c)), plus 1.0% of GP, LLC’s domestic bonus and unit compensation expense.

(d) “Person” means an individual or a corporation, limited liability company, partnership, joint venture, trust, unincorporated organization or other enterprise (including an employee benefit plan), association, government agency or political subdivision thereof or other entity.

ARTICLE II

PROVISION OF SERVICES

Section 2.1 Provision of Services by GP, LLC.

In accordance with Section 7.1 of the Partnership Agreement, GP, LLC shall provide all executive management, accounting, legal, cash management, corporate finance and other administrative services necessary and appropriate, in its sole discretion, to conduct the business of NuStar Energy (the “Services”). Nothing herein shall prevent GP, LLC from providing all executive management, accounting, legal, cash management, corporate finance and other related administrative services necessary to conduct the business of Holdings or any Affiliate of Holdings or GP, LLC.

Section 2.2 Reimbursement for Services.

(a) Reimbursement for Services. Commencing on the Effective Date of this Agreement, NuStar Energy shall promptly reimburse GP, LLC for all payroll and related expenses it incurs (including salary, bonus, incentive compensation, pension, benefits costs and other amounts paid to any Person including Affiliates of GP, LLC) (the “Services Reimbursement”), minus (a) the Holdings Administrative Services Fee and (b) any other services fee or similar charge to any other entity, including foreign Affiliates of GP, LLC.

(b) Taxes. If the Services Reimbursement does not include sales, use, excise, value added or similar taxes, if any such taxes are imposed on the Services, and if under the applicable laws any such taxes are to be collected and remitted to the appropriate authorities by GP, LLC, NuStar Energy shall pay or reimburse GP, LLC for any such taxes.

- 2 -

(c) Adjustment to Holdings Administrative Services Fee. The Holdings Administrative Services Fee is subject to adjustment as follows: (i) by an annual amount equal to GP, LLC’s annual merit increase percentage for the most recently completed fiscal year and (ii) for changed levels of services due to expansion of operations through expansion of operations, acquisition or construction of new businesses or assets or otherwise.

Section 2.3 Term.

(a) Initial Term. This Agreement shall have an initial term commencing on the Effective Date and continuing in full force and effect until December 31, 2012, unless otherwise terminated pursuant to the terms hereof.

(b) Renewal. This Agreement shall be renewed automatically for additional successive two-year terms after the Initial Term, unless either party provides six months’ advance notice to the other party of its intent to terminate this Agreement, in which case this Agreement shall terminate six months after such notice is delivered.

ARTICLE III

MISCELLANEOUS

Section 3.1 No Third Party Beneficiary. The provisions of this Agreement are enforceable solely by the parties to the Agreement and no limited partner, assignee, member or other person shall have the right, separate and apart from the parties hereto, to enforce any provisions of this Agreement or to compel any party to this Agreement to comply with the terms of this Agreement.

Section 3.2 Limited Warranty; Limitation of Liability.

GP, LLC represents that it will provide or cause the services to be provided to NuStar Energy with reasonable care and in accordance with all applicable laws, rules, and regulations, including without limitation those of the Federal Energy Regulatory Commission. EXCEPT AS SET FORTH IN THE IMMEDIATELY PRECEDING SENTENCE, ALL PRODUCTS OBTAINED FOR NUSTAR ENERGY AND ITS AFFILIATES ARE AS IS, WHERE IS, WITH ALL FAULTS AND GP, LLC MAKES NO (AND HEREBY DISCLAIMS AND NEGATES ANY AND ALL) REPRESENTATIONS AND WARRANTIES, EXPRESS OR IMPLIED, INCLUDING THE WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE WITH RESPECT TO THE SERVICES RENDERED OR PRODUCTS OBTAINED FOR NUSTAR ENERGY AND ITS AFFILIATES. FURTHERMORE, NUSTAR ENERGY AND ITS AFFILIATES MAY NOT RELY UPON ANY REPRESENTATION OR WARRANTY, EXPRESS OR IMPLIED, INCLUDING THE WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE MADE TO GP, LLC BY ANY PARTY PERFORMING SERVICES ON BEHALF OF GP, LLC HEREUNDER, UNLESS SUCH PARTY MAKES AN EXPRESS WARRANTY TO NUSTAR ENERGY AND ITS AFFILIATES. HOWEVER, IN THE CASE OF SERVICES PROVIDED BY A THIRD PARTY FOR NUSTAR ENERGY AND ITS AFFILIATES, IF THE THIRD PARTY PROVIDER OF SUCH SERVICES MAKES AN EXPRESS WARRANTY TO NUSTAR ENERGY AND ITS AFFILIATES, NUSTAR ENERGY AND ITS AFFILIATES ARE ENTITLED TO CAUSE GP, LLC TO RELY ON AND TO ENFORCE SUCH WARRANTY.

- 3 -

IT IS EXPRESSLY UNDERSTOOD BY NUSTAR ENERGY AND ITS AFFILIATES THAT GP, LLC SHALL HAVE NO LIABILITY FOR THE FAILURE OF THIRD PARTY PROVIDERS TO PERFORM ANY SERVICES HEREUNDER AND FURTHER THAT GP, LLC SHALL HAVE NO LIABILITY WHATSOEVER FOR THE SERVICES PROVIDED BY ANY SUCH THIRD PARTY UNLESS IN EITHER EVENT SUCH SERVICES ARE PROVIDED IN A MANNER WHICH WOULD EVIDENCE GROSS NEGLIGENCE OR INTENTIONAL MISCONDUCT ON THE PART OF GP, LLC BUT GP, LLC SHALL, ON BEHALF OF NUSTAR ENERGY AND ITS AFFILIATES, PURSUE ALL RIGHTS AND REMEDIES UNDER ANY SUCH THIRD PARTY CONTRACT. NUSTAR ENERGY AND ITS AFFILIATES AGREES THAT THE REMUNERATION PAID TO GP, LLC HEREUNDER FOR THE SERVICES TO BE PERFORMED REFLECT THIS LIMITATION OF LIABILITY AND DISCLAIMER OF WARRANTIES. IN NO EVENT SHALL GP, LLC BE LIABLE TO NUSTAR ENERGY, ITS AFFILIATES OR ANY OTHER PERSON FOR ANY INDIRECT, SPECIAL, OR CONSEQUENTIAL DAMAGES RESULTING FROM ANY ERROR IN THE PERFORMANCE OF SERVICES OR FROM THE BREACH OF THIS AGREEMENT, REGARDLESS OF THE FAULT OF GP, LLC OR ANY THIRD PARTY PROVIDER OR WHETHER GP, LLC OR THE THIRD PARTY PROVIDER ARE WHOLLY, CONCURRENTLY, PARTIALLY, OR SOLELY NEGLIGENT. TO THE EXTENT ANY THIRD PARTY PROVIDER HAS LIMITED ITS LIABILITY TO GP, LLC FOR SERVICES UNDER AN OUTSOURCING OR OTHER AGREEMENT, NUSTAR ENERGY AND ITS AFFILIATES AGREE TO BE BOUND BY SUCH LIMITATION OF LIABILITY FOR ANY PRODUCT OR SERVICE PROVIDED TO NUSTAR ENERGY AND ITS AFFILIATES BY SUCH THIRD PARTY PROVIDER UNDER GP, LLC’S AGREEMENT.

Section 3.3 Force Majeure. If either party to this Agreement is rendered unable by force majeure to carry out its obligations under this Agreement, other than a party’s obligation to make payments as provided for herein, that party shall give the other party prompt written notice of the force majeure with reasonably full particulars concerning it. Thereupon, the obligations of the party giving the notice, insofar as they are affected by the force majeure, shall be suspended during, but no longer than the continuance of, the force majeure. The affected party shall use all reasonable diligence to remove or remedy the force majeure situation as quickly as practicable.

The requirement that any force majeure situation be removed or remedied with all reasonable diligence shall not require the settlement of strikes, lockouts or other labor difficulty by the party involved, contrary to its wishes. Rather, all such difficulties may be handled entirely within the discretion of the party concerned.

Section 3.4 Further Assurances. In connection with this Agreement and all transactions contemplated by this Agreement, each signatory party hereto agrees to execute and deliver such additional documents and instruments as may be required for a party to provide the services hereunder and to perform such other additional acts as may be necessary or appropriate to effectuate, carry out, and perform all of the terms and provisions of this Agreement.

- 4 -

Section 3.5 Notices. Any notice, request, demand, direction or other communication required or permitted to be given or made under this Agreement to a party shall be in writing and may be given by hand delivery, postage prepaid first-class mail delivery, delivery by a reputable international courier service guaranteeing next business day delivery or by facsimile (if confirmed by one of the foregoing methods) to such party at its address noted below:

(a) in the case of GP, LLC, to:

NuStar GP, LLC

2330 North Loop 1604 West San Antonio, Texas 78248 Attention: Legal Department

Telecopy: (210)  ###-###-####

(b) in the case of NuStar Energy, to:

NuStar Energy L.P.

2330 North Loop 1604 West

San Antonio, Texas 78248

Attention: Legal Department

Telecopy: (210)  ###-###-####

or at such other address of which notice may have been given by such party in accordance with the provisions of this Section.

Section 3.6 Counterparts. This Agreement may be executed in several counterparts, no one of which needs to be executed by all of the parties. Such counterpart, including a facsimile transmission of this Agreement, shall be deemed to be an original and shall have the same force and effect as an original. All counterparts together shall constitute but one and the same instrument.

Section 3.7 Applicable Law. THIS AGREEMENT SHALL BE GOVERNED AND CONSTRUED IN ACCORDANCE WITH THE SUBSTANTIVE LAWS OF THE STATE OF TEXAS.

Section 3.8 Binding Effect; Assignment. Except for the ability of GP, LLC to cause one or more of the Services to be performed by a third party provider (subject to the terms of this Agreement), no party shall have the right to assign its rights or obligations under this Agreement (by operation of law or otherwise) without the consent of the other parties and any such assignment that is made without such consent shall be void and of no force and effect. No permitted assignment shall release any party from any of its obligations under this Agreement. All of the terms and provisions of this Agreement shall be binding upon and inure to the benefit of and be enforceable by the parties hereto and their respective successors and permitted assignees.

Section 3.9 Invalidity of Provisions. In the event that one or more of the provisions contained in this Agreement shall be invalid, illegal or unenforceable in any respect under any applicable law, the validity, legality or enforceability of the remaining provisions hereof shall not be affected or impaired thereby.

- 5 -

Section 3.10 Entire Agreement. This Agreement constitutes the whole and entire agreement between the parties hereto and supersedes any prior agreement, undertaking, declarations, commitments or representations, verbal or oral, in respect of the subject matter hereof.

Section 3.11 Captions. The captions of the sections and paragraphs of this Agreement are for convenience and reference only and in no way define, limit or describe the scope of intent of this Agreement.

[Signature Page to Follow]

- 6 -

IN WITNESS WHEREOF, the parties have caused this Agreement to be duly executed as of the date first written above.

- 7 -