Exhibit 4.1

EXECUTION VERSION

SECOND AMENDMENT TO THIRD AMENDED AND RESTATED RIGHTS AGREEMENT

This Second Amendment to Third Amended and Restated Rights Agreement (the “Amendment”) by and between Harvest Natural Resources, Inc., a Delaware corporation (the “Company”), and Wells Fargo Bank, N.A., a California corporation (the “Rights Agent”), is made and entered into as of February 1, 2013.

RECITALS

WHEREAS, the Company and the Rights Agent are parties to the Third Amended and Restated Rights Agreement, dated as of August 23, 2007, as amended by the Amendment to Third Amended and Restated Rights Agreement, dated as of October 28, 2010 (as so amended, restated and further amended, the “Rights Agreement”); and

WHEREAS, the Company wishes to amend the Rights Agreement in certain respects regarding the beneficial ownership of Common Shares of the Company by MSD Capital, L.P. and its Affiliates and Associates and the status of MSD Capital, L.P. and its Affiliates and Associates as an “Acquiring Person”, as such term is defined in the Rights Agreement.

NOW, THEREFORE, in consideration of the foregoing and for other good and valuable consideration, the parties hereto hereby agree as follows:

1. Section 1(a) of the Rights Agreement.

(a) Section 1(a) of the Rights Agreement is hereby amended and restated to provide in its entirety as follows:

“(a) A Person shall be deemed an “Acquiring Person” as set forth in subsections (i), (ii) and (iii) below:

(i) Except as otherwise provided in subsection 1(a)(ii) or (iii) below, “Acquiring Person” shall mean any Person (as such term is hereinafter defined) who or which, together with all Affiliates and Associates (as such terms are hereinafter defined) of such Person, shall be the Beneficial Owner (as such term is hereinafter defined) of 15% or more of the Common Shares then outstanding, but shall not include the Company, any Subsidiary (as such term is hereinafter defined) of the Company, any employee benefit plan of the Company or any Subsidiary of the Company, or any entity holding Common Shares for or pursuant to the terms of any such plan.

(ii) Notwithstanding the foregoing, except as set forth in subsection 1(a)(iii) below, no Person shall be deemed to be an Acquiring Person either (A) as the result of an acquisition of Common Shares by the Company which, by reducing the number of Common Shares outstanding, increases the proportionate number of Common Shares owned by such Person to 15% or more of the Common Shares of the Company then outstanding; provided, however, that if a Person shall become the Beneficial Owner of 15% or more of the Common Shares then

1

outstanding by reason of share purchases by the Company and shall, after such share purchases by the Company, become the Beneficial Owner of any additional Common Shares of the Company, then such Person shall be deemed to be an Acquiring Person, (B) if within five Business Days (as such term is hereinafter defined) after such Person would otherwise have become an Acquiring Person (but for the operation of this clause (B)), such Person notifies the Board of Directors of the Company that such Person did so and within two Business Days after such notification such Person is the Beneficial Owner of less than 15% of the outstanding Common Shares of the Company, or (C) if within ten Business Days (as such term is hereinafter defined) after the Company learns that such Person would otherwise have become an Acquiring Person (but for the operation of this clause (C)), the Company’s Board of Directors determines, by duly adopted resolution, that such Person should not be deemed an Acquiring Person and adopts and approves a supplement to this Agreement pursuant to Section 27 exempting such Person from being deemed an Acquiring Person, with such conditions, if any, that the Board of Directors deems appropriate.

(iii) Notwithstanding the foregoing subsections 1(a)(i) and (ii), MSD Capital, L.P. (“MSD”), MSDC Management, L.P. (“MSDC”) and their respective Affiliates and Associates (as such terms are hereinafter defined), shall not be deemed to be an Acquiring Person as long as MSD, MSDC and their respective Affiliates and Associates, shall be the Beneficial Owner of less than 15% of the Common Shares outstanding; provided, however, that MSD, MSDC and their respective Affiliates and Associates, shall not be deemed to be an Acquiring Person as the result of (A) any acquisition of Common Shares by the Company which, by reducing the number of Common Shares outstanding, increases proportionate number of Common Shares owned by MSD, MSDC and their respective Affiliates and Associates, to 15% or more, (B) any anti-dilution or other adjustments to any convertible securities (including convertible notes and warrants) held by MSD, MSDC or their respective Affiliates and Associates which increase the proportionate number of Common Shares owned by MSD, MSDC and their respective Affiliates and Associates, to 15% or more and (C) MSD, MSDC or their respective Affiliates and Associates inadvertently becoming an Acquiring Person as the result of the acquisition of additional Common Shares and such party or parties so notify the Board of Directors of the Company within five business days and within two business days after such notice divests itself of such additional Common Shares.”

2. Other Terms of the Rights Agreement. Except as otherwise provided in this Amendment, all other terms of the Rights Agreement shall remain in full force and effect. All references in the Rights Agreement to “this Agreement” shall be read as references to the Rights Agreement, as amended by this Amendment, but references to the date of the Rights Agreement shall remain references to August 23, 2007.

3. Counterparts. This Amendment may be executed by the parties hereto in separate counterparts, each of which when so executed and delivered shall be an original, but all such counterparts shall together constitute one and the same instrument. Each counterpart may consist of a number of copies hereof each signed by less than all, but together signed by all of the parties hereto.

4 Choice of Law. The parties intend that the laws of the State of Delaware shall govern the validity of this Amendment, the construction of its terms and the interpretation of the rights and duties of the parties hereto, without regard to conflict of laws provisions.

(The remainder of this page intentionally left blank.)

2

IN WITNESS WHEREOF, the parties have executed this Amendment as of February 1, 2013.

(Signature page to Second Amendment to Third Amended and Restated Rights Agreement)