Exhibit 10.1

AMENDED AND RESTATED K-SEA TRANSPORTATION PARTNERS L.P.

LONG-TERM INCENTIVE PLAN

1.             Purpose of the Plan.

The K-Sea Transportation Partners L.P. Long-Term Incentive Plan (the “Plan”) is intended to promote the interests of K-Sea Transportation Partners L.P., a Delaware limited partnership (the “Partnership”), by providing to employees and directors of K-Sea General Partner GP LLC, a Delaware limited liability company (the “Company”), and its Affiliates who perform services for the Partnership, incentive compensation awards for superior performance that are based on Units.  The Plan is also contemplated to enhance the ability of the Company and its Affiliates to attract and retain the services of individuals who are essential for the growth and profitability of the Partnership and to encourage them to devote their best efforts to the business of the Partnership, thereby advancing the interests of the Partnership.

2.             Definitions.

As used in the Plan, the following terms shall have the meanings set forth below:

“Affiliate” means, with respect to any Person, any other Person that directly or indirectly through one or more intermediaries controls, is controlled by or is under common control with, the Person in question. As used herein, the term “control” means the possession, direct or indirect, of the power to direct or cause the direction of the management and policies of a Person, whether through ownership of voting securities, by contract or otherwise.

“Award” means an Option or Phantom Unit granted under the Plan, and shall include any DER granted with respect to a Phantom Unit.

“Award Agreement” means the agreement entered into between the Partnership and the Participant evidencing the terms and conditions of the Award.

“Board” means the Board of Directors of the Company.

“Cash-Out Value” means the amount determined in Clause (i) or (ii), whichever is applicable, as follows: (i) the per Unit price offered to equityholders of the Partnership in any merger or consolidation or (iii) in the event of a reorganization, the Fair Market Value per Unit determined by the Committee as of the date determined by the Committee to be the date of cancellation and surrender of an Award.  In the event that the consideration offered to equityholders of the Partnership in any transaction described in this definition consists of anything other than cash, the Committee shall determine the fair cash equivalent of the portion of the consideration offered which is other than cash.

“Change in Control” shall be deemed to have occurred upon the occurrence of one or more of the following events: (i) any sale, lease, exchange or other transfer (in one or a series of related transactions) of all or substantially all of the assets of the Partnership or K-Sea Operating Partnership L.P. to any Person or its Affiliates, other than the Partnership, the

1

Company or any of their Affiliates or (ii) any merger, reorganization, consolidation or other transaction pursuant to which more than 50% of the combined voting power of the equity interests in the Partnership or K-Sea Operating Partnership L.P. ceases to be owned by Persons who own such interests, respectively, as of the date of the initial public offering of Units.

“Committee” means the Compensation Committee of the Board or such other committee of the Board appointed by the Board to administer the Plan.

“Deferral Commitment” means the agreement by which an Employee or Director, who has been issued a Phantom Unit, elects to defer receipt of the Unit or Cash-Out Value payment otherwise payable to the Employee or Director upon the vesting of the Phantom Unit.

“Deferred Award” means (i) an Elective Deferral Award (as defined in Section 6(b)(iv) of the Plan) with respect to which a recipient has made a Deferral Commitment (ii) an Automatic Deferral Award (as defined in Section 6(b)(v) of the Plan) or (iii) an Other Deferred Award (as defined in Section 6(b)(vi).

“Deferred Compensation Plan” means the K-Sea Transportation Partners L.P. Deferred Compensation Plan.

“DER” means a right, granted in tandem with a Phantom Unit, to receive an amount in cash equal to, and at the same time as, the cash distributions made by the Partnership with respect to a Unit during the period such Phantom Unit is outstanding, provided that any payments with respect to DERs that are granted in tandem with a Deferred Award may, pursuant to the terms of a Deferral Commitment or Award Agreement, be deferred under and in accordance with the Deferred Compensation Plan.

“Director” means a member of the Board or the board of directors or managers of an Affiliate who is not an Employee.

“Employee” means any employee of the Company or an Affiliate, including, without limitation, K-Sea Transportation Inc., a Delaware corporation, in each case as determined by the Committee. Notwithstanding the foregoing, the term “Employee” shall not include any individual covered by a collective bargaining or comparable agreement between representatives of such employees and the Partnership, the Company or any Affiliate of the Partnership or the Company.

“Exchange Act” means the Securities Exchange Act of 1934, as amended.

“Fair Market Value” means the closing sales price of a Unit on the date of determination (or, if there is no trading in the Units on such date, the closing sales price on the last date the Units were traded) as reported in The Wall Street Journal (or other reporting service approved by the Committee). In the event Units are not publicly traded at the time a determination of Fair Market Value is required to be made hereunder, the determination of Fair Market Value shall be made in good faith by the Committee.

“Option” means an option to purchase Units granted under the Plan.

2

“Participant” means any Employee or Director granted an Award under the Plan.

“Partnership Agreement” means the First Amended and Restated Agreement of Limited Partnership of the Partnership.

“Person” means an individual or a corporation, limited liability company, partnership, joint venture, trust, unincorporated organization, association, governmental agency or political subdivision thereof or other entity.

“Phantom Unit” means a phantom (notional) unit granted under the Plan which upon vesting, or at such other time as may be specified in a Deferral Commitment or Award Agreement, entitles the Participant to receive a Unit or an amount of cash equal to the Fair Market Value of a Unit, whichever is determined by the Committee.

“Plan” means this K-Sea Transportation Partners L.P. Long-Term Incentive Plan, as amended from time to time.

“Restricted Period” means the period established by the Committee with respect to an Award during which the Award remains subject to forfeiture (i.e., it is not vested) and is not exercisable by or payable to the Participant.

“Rule 16b-3” means Rule 16b-3 promulgated by the SEC under the Exchange Act, or any successor rule or regulation thereto as in effect from time to time.

“SEC” means the Securities and Exchange Commission, or any successor thereto.

“Unit” means a Common Unit of the Partnership.

3.             Administration.

The Plan shall be administered by the Committee. A majority of the Committee shall constitute a quorum, and the acts of the members of the Committee who are present at any meeting thereof at which a quorum is present, or acts unanimously approved by the members of the Committee in writing, shall be the acts of the Committee. Subject to the following and any applicable law, the Committee, in its sole discretion, may delegate any or all of its powers and duties under the Plan, including the power to grant Awards under the Plan, to the Chief Executive Officer of K-Sea Transportation GP, LLC (provided that the Chief Executive Officer is a member of the Board), subject to such limitations on such delegated powers and duties as the Committee may impose, if any. Upon any such delegation all references in the Plan to the “Committee,” other than in Section 7, shall be deemed to include the Chief Executive Officer; provided, however, that such delegation shall not limit the Chief Executive Officer’s right to receive Awards under the Plan. Notwithstanding the foregoing, the Chief Executive Officer may not grant Awards to, or take any action with respect to any Award previously granted to, himself, a person who is an officer subject to Rule 16b-3 or who is a member of the Board.  Subject to the terms of the Plan and applicable law, and in addition to other express powers and authorizations conferred on the Committee by the Plan, the Committee shall have full power and authority to: (i) designate Participants; (ii) determine the type or types of Awards to be granted to a Participant; (iii) determine the number of Units to be covered by Awards; (iv) determine the

3

terms and conditions of any Award; (v) determine whether, to what extent, and under what circumstances Awards may be settled, exercised, canceled, or forfeited; (vi) interpret and administer the Plan and any instrument or agreement relating to an Award made under the Plan; (vii) establish, amend, suspend, or waive such rules and regulations and appoint such agents as it shall deem appropriate for the proper administration of the Plan; and (viii) make any other determination and take any other action that the Committee deems necessary or desirable for the administration of the Plan. Unless otherwise expressly provided in the Plan, all designations, determinations, interpretations, and other decisions under or with respect to the Plan or any Award shall be within the sole discretion of the Committee, may be made at any time and shall be final, conclusive, and binding upon all Persons, including the Company, the Partnership, any Affiliate, any Participant, and any beneficiary of any Award.

4.             Units.

(a)           Units Available. Subject to adjustment as provided in Section 4(c), the number of Units with respect to which Options and Phantom Units may be granted under the Plan is 940,000.  If any Option or Phantom Unit is forfeited or otherwise terminates or is canceled without the delivery of Units, then the Units covered by such Award, to the extent of such forfeiture, termination or cancellation, shall again be Units with respect to which an Option or Phantom Unit, as the case may be, may be granted.

(b)           Sources of Units Deliverable Under Awards.  Any Units delivered pursuant to an Award shall consist, in whole or in part, of Units acquired in the open market, from any Affiliate, or from the Partnership, or any combination of the foregoing, as determined by the Committee in its discretion.

(c)           Adjustments. In the event that the Committee determines that any distribution (whether in the form of cash, Units, other securities, or other property), recapitalization, split, reverse split, reorganization, merger, consolidation, split-up, spin-off, combination, repurchase, or exchange of Units or other securities of the Partnership, issuance of warrants or other rights to purchase Units or other securities of the Partnership, or other similar transaction or event affects the Units such that an adjustment is determined by the Committee to be appropriate in order to prevent dilution or enlargement of the benefits or potential benefits intended to be made available under the Plan, then the Committee shall, in such manner as it may deem equitable, adjust any or all of (i) the number and type of Units (or other securities or property) with respect to which Awards may be granted, (ii) the number and type of Units (or other securities or property) subject to outstanding Awards, and (iii) the grant or exercise price with respect to any Award or, if deemed appropriate, make provision for a cash payment to the holder of an outstanding Award; provided that the number of Units subject to any Award shall always be a whole number.

(d)           Cash-Out of Awards. In the event that the Partnership is reorganized, merged or consolidated with another entity, the Committee may, in its sole discretion, (i) require the mandatory surrender to the Partnership by selected holders of Options of some or all of the outstanding Options held by such holder (irrespective of whether such Options are then exercisable under the provisions of the Plan) as of a date (before or after the reorganization, merger or consolidation) specified by the Committee, in which event the Committee shall

4

thereupon cancel such Options and pay to each holder thereof an amount of cash per Unit equal to the excess, if any, of the Cash-Out Value of the Units subject to such Option over the exercise price(s) under such Options for such Units or (ii) require the mandatory surrender to the Partnership by selected holders of Phantom Units of some or all of the outstanding Phantom Units held by such holder (irrespective of whether such Phantom Units are vested under the provisions of the Plan) as of a date (before or after the reorganization, merger or consolidation) specified by the Committee, in which event the Committee shall thereupon cancel such Phantom Units and pay to each holder an amount of cash per Phantom Unit equal to the Cash-Out Value of the Units. Notwithstanding the above, with respect to Phantom Unit Awards that constitute nonqualified deferred compensation within the meaning of Section 409A of the Internal Revenue Code of 1986, as amended, and the regulations and other applicable authority thereunder (“Section 409A”) and are subject to the requirements of Section 409A, an accelerated payment of such Phantom Unit Award may only be made if the reorganization, merger or consolidation event which triggers the application of this Section 4(d) would qualify as a permitted distribution event under the then-applicable authority issued with respect to Section 409A or would otherwise be permissible under Section 409A.

5.             Eligibility.

Any Employee who performs services for the benefit of the Partnership as determined by the Committee, or any Director shall be eligible to be designated a Participant and receive an Award under the Plan.

6.             Awards.

(a)           Options.  The Committee shall have the authority to determine the Employees and Directors to whom Options shall be granted, the number of Units to be covered by each Option, the purchase price therefor, the Restricted Period and the conditions and limitations applicable to the exercise of the Option, including the following terms and conditions and such additional terms and conditions, as the Committee shall determine, that are not inconsistent with the provisions of the Plan.

(i)            Exercise Price.  The purchase price per Unit purchasable under an Option shall be determined by the Committee at the time the Option is granted and may not be less than its Fair Market Value as of the date of grant.

(ii)           Time and Method of Exercise.  The Committee shall determine the Restricted Period with respect to an Option, which may include, without limitation, accelerated vesting upon the achievement of specified performance goals, and the method or methods by which payment of the exercise price with respect thereto be made or deemed to have been made, which may include, without limitation: (a) cash, (b) check acceptable to the Company, (c) a “cashless-broker” exercise through procedures approved by the Company or (d) any combination thereof, having a Fair Market Value on the exercise date equal to the relevant exercise price.

5

(iii)          Forfeiture.  Except as otherwise provided in the terms of the Option grant, upon termination of a Participant’s employment with the Company and its Affiliates or membership on the Board, whichever is applicable, for any reason during the applicable Restricted Period, all Options shall be forfeited by the Participant (or any transferee) unless otherwise provided in a written employment agreement between the Participant and the Company or its Affiliates. The Committee may, in its discretion, waive in whole or in part such forfeiture with respect to a Participant’s Options.

(b)           Phantom Units. The Committee shall have the authority to determine the Employees and Directors to whom Phantom Units shall be granted, the number of Phantom Units to be granted to each such Participant, the Restricted Period, the conditions under which the Phantom Units may become vested or forfeited, which may include, without limitation, the accelerated vesting upon the achievement of specified performance goals, and such other terms and conditions as the Committee may establish with respect to such Awards including whether DERs are granted with respect to such Phantom Units.

(i)            DERs.  Phantom Units granted under the Plan may include a tandem DER grant.

(ii)           Forfeiture.  Except as otherwise provided in the terms of the Phantom Units grant, upon termination of a Participant’s employment with the Company and its Affiliates or membership on the Board, whichever is applicable, for any reason during the applicable Restricted Period, all Phantom Units shall be forfeited by the Participant (or any transferee) unless otherwise provided in a written employment agreement between the Participant and the Company or its Affiliates. The Committee may, in its discretion, waive in whole or in part such forfeiture with respect to a Participant’s Phantom Units.

(iii)          Lapse of Restrictions.  Unless a different payment time is specified in the Award agreement, the Participant shall be entitled to receive from the Company one Unit or cash equal to the Fair Market Value of a Unit, as determined by the Committee, in its discretion, upon or as soon as reasonably practical following the vesting of each Phantom Unit.

(iv)          Elective Deferral Awards.  The Committee may, pursuant to the terms of an Award Agreement, permit the recipient of a Phantom Unit award, within 30 days from the date of receipt of such Phantom Unit award, in his or her sole discretion, to execute a written Deferral Commitment specifying that the Phantom Unit award shall not be paid to the recipient upon the vesting of the Phantom Unit award but shall instead be deferred pursuant to the terms of such Deferral Commitment and the terms of the Deferred Compensation Plan (any such award pursuant to which a recipient may execute a Deferral Commitment, an “Elective Deferral Award”).  Notwithstanding the terms of any Elective Deferral Award or any employment or other agreement to which a recipient may be a party to the contrary, except in connection with any applicable vesting acceleration in connection with a Change in Control that also constitutes a change in control

6

event (within the meaning of Treasury Regulation Section 1.409A-3(i)(5) or any successor regulation) or a recipient’s disability (within the meaning of Treasury Regulation Section 1.409A-3(i)(4)) or a recipient’s death, in no event shall any Phantom Units that are subject to an Elective Deferral Award vest prior to the 31st day following the one-year anniversary of the date of grant of such Elective Deferral Award, regardless of whether the recipient makes a Deferral Commitment with respect to such Elective Deferral Award.  If a recipient makes a Deferral Commitment with respect to any Phantom Units that are subject to an Elective Deferral Award, and the recipient becomes entitled to accelerated vesting with respect to such Phantom Units as a result of a Qualified Acceleration Event that occurs prior to the one-year anniversary of the date the recipient makes the applicable Deferral Commitment, such Deferral Commitment shall not be given effect and such Phantom Units shall not constitute a Deferred Award.

(v)           Automatic Deferral Awards. The Committee may, pursuant to the terms of an Award Agreement, grant Phantom Units under the Plan that are automatically deferred under and in accordance with the terms of the Deferred Compensation Plan (an “Automatic Deferral Award”).  In the event the Committee grants an Automatic Deferral Award to a recipient, the Award Agreement with respect to such Automatic Deferral Award shall constitute the recipient’s Deferral Commitment for purposes of the Deferred Compensation Plan.

(vi)          Other Deferred Awards.  The Committee may permit a recipient to make a Deferral Commitment with respect to any grant or potential grant of Phantom Units in such other manner as the Committee may determine from time to time, provided that such Deferral Commitment complies with the terms of the Deferred Compensation Plan and Section 409A. Any Phantom Unit award with respect to which such a Deferral Commitment has been made is referred to herein as an “Other Deferred Award.”

(c)           General.

(i)            Awards May Be Granted Separately or Together. Awards may, in the discretion of the Committee, be granted either alone or in addition to, in tandem with, or in substitution for any other Award granted under the Plan or any award granted under any other plan of the Company or any Affiliate. Awards granted in addition to or in tandem with other Awards or awards granted under any other plan of the Company or any Affiliate may be granted either at the same time as or at a different time from the grant of such other Awards or awards.

(ii)           Limits on Transfer of Awards.  Unless otherwise provided in the Award agreement, each Option shall be exercisable only by the Participant during the Participant’s lifetime, or by the person to whom the Participant’s right shall pass by will or the law of descent and distribution.  Unless otherwise provided in the Award agreement, no Award and no right under any such Award may be assigned, alienated, pledged, attached, sold or otherwise transferred or

7

encumbered by a Participant and any such purported assignment, alienation, pledge, attachment, sale, transfer or encumbrance shall be void and unenforceable against the Company and any Affiliate.

(iii)          Term of Awards. The term of each Award shall be for such period as may be determined by the Committee.

(iv)          Unit Certificates. All certificates for Units or other securities of the Partnership delivered under the Plan pursuant to any Award or the exercise thereof shall be subject to such stop transfer orders and other restrictions as the Committee may deem advisable under the Plan or the rules, regulations, and other requirements of the SEC, any stock exchange upon which such Units or other securities are then listed, and any applicable federal or state laws.  The Committee may cause a legend or legends to be put on any such certificates to make appropriate reference to such restrictions.

(v)           Consideration for Grants.  Awards may be granted for such consideration, including services, as the Committee determines.

(vi)          Delivery of Units or other Securities and Payment by Participant of Consideration.  Notwithstanding anything in the Plan or any grant agreement to the contrary, delivery of Units pursuant to the exercise or vesting of an Award may be deferred for any period during which, in the good faith determination of the Committee, the Company is not reasonably able to obtain Units to deliver pursuant to such Award without violating the rules or regulations of any applicable law or securities exchange. No Units or other securities shall be delivered pursuant to any Award until payment in full of any amount required to be paid pursuant to the Plan or the applicable Award Agreement (including, without limitation, any exercise price or tax withholding) is received by the Company. Such payment may be made by such method or methods and in such form or forms as the Committee shall determine, including, without limitation, cash, other Awards, withholding of Units, cashless-broker exercises with simultaneous sale, or any combination thereof; provided that the combined value, as determined by the Committee, of all cash and cash equivalents and the Fair Market Value of any such Units or other property so tendered to the Company, as of the date of such tender, is at least equal to the full amount required to be paid to the Company pursuant to the Plan or the applicable Award agreement.

(vii)         Change in Control.  Subject to additional or contrary provisions in the Award agreement, upon a Change in Control or such period prior thereto as may be established by the Committee, all Awards shall automatically vest and become payable or exercisable, as the case may be, in full. In this regard, all Restricted Periods shall terminate and all performance criteria, if any, shall be deemed to have been achieved at the maximum level. To the extent an Option is not exercised upon a Change in Control, the Committee may, in its discretion, cancel such Award without payment or provide for a replacement grant with respect to such Award on such terms as it deems appropriate.

8

7.             Amendment and Termination.

Except to the extent prohibited by applicable law:

(a)           Amendments to the Plan.  Except as required by the rules of the principal securities exchange on which the Units are traded and subject to Section 7(b) below, the Board or the Committee may amend, alter, suspend, discontinue, or terminate the Plan in any manner, including increasing the number of Units available for Awards under the Plan, without the consent of any partner, Participant, other holder or beneficiary of an Award, or other Person.

(b)           Amendments to Awards.  Subject to Section 7(a), the Committee may waive any conditions or rights under, amend any terms of, or alter any Award theretofore granted, provided no change, other than pursuant to Section 7(c), in any Award shall materially reduce the benefit to a Participant without the consent of such Participant.

(c)           Adjustment of Awards Upon the Occurrence of Certain Unusual or Nonrecurring Events.  The Committee is hereby authorized to make adjustments in the terms and conditions of, and the criteria included in, Awards in recognition of unusual or nonrecurring events (including, without limitation, the events described in Section 4(c) of the Plan) affecting the Partnership or the financial statements of the Partnership, or of changes in applicable laws, regulations, or accounting principles, whenever the Committee determines that such adjustments are appropriate in order to prevent dilution or enlargement of the benefits or potential benefits intended to be made available under the Plan.

8.             General Provisions.

(a)           No Rights to Award. No Person shall have any claim to be granted any Award under the Plan, and there is no obligation for uniformity of treatment of Participants. The terms and conditions of Awards need not be the same with respect to each recipient.

(b)           Withholding. The Company, its Affiliate or its designated third party administrator shall have the right to deduct applicable taxes from any Award payment and withhold, at the time of delivery or vesting of cash or Units under this Plan, an appropriate amount of cash or number of Units or a combination thereof for payment of taxes or other amounts required by law or to take such other action as may be necessary in the opinion of the Company or its Affiliate to satisfy all obligations for withholding of such taxes. The Committee may also permit withholding to be satisfied by the transfer to the Company or its Affiliate of Units theretofore owned by the holder of the Award with respect to which withholding is required.  If Units are used to satisfy tax withholding, such Units shall be valued based on the Fair Market Value when the tax withholding is required to be made.

(c)           No Right to Employment.  The grant of an Award shall not be construed as giving a Participant the right to be retained in the employ of the Company or any Affiliate or to remain on the Board, as applicable. Further, the Company or an Affiliate may at any time dismiss a Participant from employment.

9

(d)           Governing Law. The validity, construction, and effect of the Plan and any rules and regulations relating to the Plan shall be determined in accordance with the laws of the State of Delaware without regard to its conflict of laws principles.

(e)           Severability. If any provision of the Plan or any Award becomes invalid, illegal, or unenforceable in any jurisdiction or as to any Person or Award, or would disqualify the Plan or any Award under any law deemed applicable by the Committee, such provision shall be deemed amended to conform to the applicable laws, or if it cannot be construed or deemed amended without materially altering the intent of the Plan or the Award, such provision shall be stricken as to such jurisdiction, person or Award and the remainder of the Plan and any such Award shall remain in full force and effect.

(f)            Other Laws. Notwithstanding anything in the Plan or any Award agreement to the contrary, the Committee may refuse to issue or transfer any Units or other consideration under an Award if, in its sole discretion, it determines that the issuance or transfer of such Units or such other consideration might violate any applicable law or regulation, the rules of the principal securities exchange on which the Units are then traded.

(g)           No Trust or Fund Created.  Neither the Plan nor any Award shall create or be construed to create a trust or separate fund of any kind or a fiduciary relationship between the Company or any participating Affiliate and a Participant or any other Person. To the extent that any Person acquires a right to receive payments from the Company or any participating Affiliate pursuant to an Award, such right shall be no greater than the right of any general unsecured creditor of the Company or any participating Affiliate.

(h)           No Fractional Units.  No fractional Units shall be issued or delivered pursuant to the Plan or any Award, and the Committee shall determine whether cash, other securities, or other property shall be paid or transferred in lieu of any fractional Units or whether such fractional Units or any rights thereto shall be canceled, terminated, or otherwise eliminated.

(i)            Headings. Headings are given to the Sections and subsections of the Plan solely as a convenience to facilitate reference. Such headings shall not be deemed in any way material or relevant to the construction or interpretation of the Plan or any provision thereof.

(j)            Facility of Payment. Any amounts payable hereunder to any individual under legal disability or who, in the judgment of the Committee, is unable to properly manage his financial affairs, may be paid to the legal representative of such person, or may be applied for the benefit of such person in any manner that the Committee may select, and the Company and its Affiliates shall be relieved of any further liability for payment of such amounts.

(k)           Gender and Number. Words in the masculine gender shall include the feminine gender, the plural shall include the singular and the singular shall include the plural.

9.             Term of the Plan.

The Plan shall be effective on the date of its approval by the Board and shall continue until the date terminated by the Board or the date Units are no longer available for the payment of Awards under the Plan, whichever occurs first. However, unless otherwise expressly

10

provided in the Plan or in an applicable Award Agreement, any Award granted prior to such termination, and the authority of the Board or the Committee to amend, alter, adjust, suspend, discontinue, or terminate any such Award or to waive any conditions or rights under such Award, shall extend beyond such termination date.

11