EXCHANGE AGREEMENT

Exhibit 10.4

EXCHANGE AGREEMENT

THIS IS AN EXCHANGE AGREEMENT, dated as of January 8, 2007 (the “Agreement”), among Seitel Holdings, LLC, a Delaware limited liability company (the “Company”), the individuals listed on the signature pages hereto as “Management Investors” (such individuals, the “Management Investors,” and each such individual, a “Management Investor”).

BACKGROUND

A. This Agreement is being entered into in anticipation of the consummation of the transactions contemplated by the Agreement and Plan of Merger, dated as of October 31, 2006 (the “Merger Agreement“), by and among the Company, Seitel Acquisition Corp., a Delaware corporation (“Merger Sub“) and Seitel, Inc., a Delaware corporation (“Seitel”).

B. Pursuant to the terms of the Merger Agreement, Merger Sub will be merged with and into Seitel with Seitel surviving as a wholly-owned subsidiary of the Company. The Company is expected to be converted to a Delaware corporation concurrently with the completion of the Merger (such time concurrent with the completion of the Merger as of which such conversion has been effected, the “Effective Time”).

C. The Management Investors own the shares of Common Stock, par value $0.01, of Seitel (the “Seitel Common Stock”) set forth on Schedule I hereto (such shares of Seitel Common Stock owned by the Management Investors are referred to herein as “Shares”).

D. Immediately prior to the consummation of the Merger, the Management Investors desire to exchange (the “Exchange”) their respective Shares set forth on Schedule II hereto (the “Exchange Shares”) for the right to receive at the Effective Time the shares of the Common Stock, par value $0.001 per share, of the Company set forth on Schedule II hereto (the “New Shares”), having the terms set forth in the Certificate of Incorporation attached hereto as Exhibit A (the “Certificate of Incorporation”), and the Company is willing to effect such Exchange at the Effective Time, upon the terms and subject to the conditions provided herein.

Terms

In consideration for the various agreements contained herein, the parties hereto agree as follows:

ARTICLE 1

EXCHANGE

Section 1.1. Exchange. Upon the terms and subject to the conditions of this Agreement, (i) each Management Investor hereby agrees to transfer, assign, deliver and contribute to the Company, and the Company hereby agrees to accept delivery and contribution of, immediately prior to the Closing (as such term is defined in the Merger Agreement), all of each Management Investor’s respective Exchange Shares in exchange for the right to issuance by the Company, at the Effective Time, of the New Shares, and (ii) the Company hereby agrees to so issue such New Shares in such Exchange at the Effective Time.

Section 1.2. Default by any Management Investor. If any Management Investor defaults in his or her obligations under this Article 1, such failure shall not relieve any other Management Investor of any obligation hereunder, and at the Company’s option, it may (a) issue the remaining New Shares contemplated to be exchanged by the Company hereunder, or (b) refuse to make any issuance or exchange and thereby terminate all of its obligations hereunder, in either case without prejudice to the Company’s rights against such defaulting Management Investor. In addition, upon such default the Company shall have the right in its sole discretion to sell or otherwise exchange or transfer any New Shares that were to be sold to such defaulting Management Investor prior to such default. For the avoidance of doubt, in no event will the termination of employment by a Management Investor prior to the Effective Time be considered a breach or default under this Agreement.

Section 1.3. Exchange Closing. Subject to the satisfaction of the conditions set forth in Article 5, the closing of the Exchange (the “Exchange Closing”) shall take place simultaneously with the Effective Time:

(a) Immediately prior to the Closing of the transactions described in the Merger Agreement, each Management Investor shall deliver to the Company certificates representing the Exchange Shares, duly endorsed or accompanied by stock powers duly endorsed in blank, with any required transfer stamps affixed thereto, and

(b) At the Exchange Closing, the Company shall deliver to each Management Investor a stock certificate(s) representing the New Shares to be issued to such Management Investor pursuant to Section 1.1, duly registered in the name of such Management Investor.

ARTICLE 2

REPRESENTATIONS, WARRANTIES AND COVENANTS OF THE COMPANY

Section 2.1. Representations, Warranties and Covenants of the Company. The Company represents and warrants to, and covenants and agrees with each Management Investor as follows:

(a) As of the date hereof, the Company is a limited liability company duly formed, validly existing and in good standing under the laws of the State of Delaware. At the Effective Time, the Company will be a corporation duly organized, validly existing and in good standing under the laws of the State of Delaware. The only business activities conducted by the Company prior to the date hereof have been in connection with the transactions contemplated by the Merger Agreement any agreement related thereto, this Agreement and any agreement related thereto and the preparation of any documents related to any such agreements, including but not limited to the transactions, agreements and documents related to the financing of any transactions contemplated by any of the foregoing.

(b) The Company has all requisite limited liability company power and authority to execute, deliver and perform this Agreement and to consummate the transactions

- 2 -

provided for herein, and at the Effective Time will have all requisite corporate power and authority to perform this Agreement and to consummate the transactions provided for herein, including, but not limited to, the issuance and exchange of the New Shares to be issued by it hereunder.

(c) The execution, delivery and performance by the Company of this Agreement and the consummation by the Company of the transactions contemplated hereby, including, but not limited to, the issuance and exchange of the New Shares to be issued by it hereunder, have been duly authorized. This Agreement has been duly and validly executed and delivered and constitutes the valid and binding obligation of the Company, enforceable against it in accordance with the terms hereof. All limited liability company action necessary for the authorization, execution and delivery of this Agreement, and all corporate action necessary for the performance of all obligations of the Company hereunder at the Exchange Closing, and the authorization, issuance, exchange and delivery of the New Shares in accordance with this Agreement has been taken or will have been taken, as applicable, prior to or concurrently with the Exchange Closing.

(d) The New Shares issued to the Management Investor under Article 1 hereof, when issued in compliance with the provisions of this Agreement, will be validly issued, fully paid and non-assessable and will be free of all mortgages, pledges, security interests, liens, charges, claims, restrictions, easements or other encumbrances of any nature other than restrictions as set forth in the Securities Holders Agreement and under applicable state and federal securities laws. The sale and exchange of the New Shares pursuant to this Agreement will not be subject to any preemptive rights or rights of first refusal.

(e) As of the Effective Time, after giving effect to the transactions contemplated by this Agreement, the authorized capital stock of the Company shall consist of 1,100,000 shares of Common Stock, 1,000,000 shares of which will be issued and outstanding at the Effective Time after giving effect to the consummation of the transactions contemplated by this Agreement.

ARTICLE 3

REPRESENTATIONS AND WARRANTIES AND COVENANTS OF EACH MANAGEMENT INVESTOR

Section 3.1. Representations, Warranties and Covenants of Each Management Investor. Each Management Investor represents and warrants to, and covenants and agrees with, the Company that:

(a) Such Management Investor has the requisite legal right, power and authority (including, if applicable, the due authorization by all necessary corporate, partnership or limited liability company action) to enter into this Agreement, to perform such Management Investor’s obligations hereunder and to consummate the transactions provided for herein without the need for the consent of any other person (including a spouse, if any, of such Management Investor); and this Agreement has been duly authorized, executed and delivered and constitutes the legal, valid and binding obligation of such Management Investor, enforceable against such Management Investor in accordance with the terms hereof. As used herein, the term “person” means an individual or a corporation, partnership, limited liability company, joint venture, trust, regulatory or governmental agency or authority or other organization or entity of any kind.

- 3 -

(b) The New Shares are being acquired by such Management Investor hereunder for investment, and not with a view to any distribution thereof that would violate the Securities Act or the applicable state securities laws of any state. Such Management Investor will not distribute the New Shares in violation of the Securities Act or the applicable securities laws of any state.

(c) Such Management Investor understands that the New Shares have not been registered under the Securities Act or the securities laws of any state and must be held indefinitely unless subsequently registered under the Securities Act and any applicable state securities laws or unless an exemption from such registration becomes or is available.

(d) In formulating a decision to enter into this Agreement, such Management Investor has relied solely upon (i) the provisions of this Agreement, (ii) an independent investigation of the Company’s business, and (iii) consultations with his or her legal and financial advisors with respect to this Agreement and the nature of his or her investment; and that in entering into this Agreement no reliance was placed by the Management Investor upon any representations or warranties other than those contained in this Agreement.

(e) Such Management Investor is financially able to hold the New Shares for long-term investment, believes that the nature and amount of the New Shares being acquired are consistent with his or her overall investment program and financial position, and recognizes that there are substantial risks involved in the acquisition of New Shares.

(f) Such Management Investor confirms that (i) he or she is familiar with the business of the Company, (ii) he or she has had the opportunity to ask questions of the officers and directors of the Company and to obtain (and that such Management Investor has received to his or her satisfaction) such information about the business and financial condition of the Company as he or she has reasonably requested, and (iii) such Management Investor, either alone or with a representative (as defined in Rule 501(h) promulgated under the Securities Act), has such knowledge and experience in financial and business matters that such Management Investor is capable of evaluating the merits and risks of the prospective investment in the New Shares.

(g) Such Management Investor confirms and acknowledges that he or she has received a copy of this contract in accordance with Rule 701 under the Securities Act.

(h) Such Management Investor confirms that he or she qualifies as an “accredited investor“ within the meaning of Rule 501(a) of Regulation D under the Securities Act under which the Management Investor (i) has a net worth of at least one million dollars ($1,000,000), (ii) has had an annual income of at least two hundred thousand dollars ($200,000), individually or joint income with spouse of three hundred thousand dollars ($300,000) for each of the last two years or (iii) is a director, executive officer, or general partner of the issuer of the securities being offered or sold.

(i) Such Management Investor’s address is as set forth in Section 6.1 hereof.

- 4 -

(j) Such Management Investor agrees to provide any information, execute any document and take any other actions reasonably requested by the Company in connection with this Agreement or the consummation of the transactions contemplated hereby in order that such transactions will comply with the applicable securities laws of any jurisdiction. Such Management Investor also agrees to execute any document with his or her spouse, if any, that the Company deems reasonably necessary to effectuate the intent of this Agreement, any securities holders agreement, registration rights agreement or other document executed in connection herewith or any of the terms of any of the foregoing.

ARTICLE 4

COVENANTS

Section 4.1. Commercially Reasonable Best Efforts; Further Assurances. The Company and each Management Investor agree to use their respective commercially reasonable best efforts to take, or cause to be taken, all appropriate action, and to do, or cause to be done, all things necessary, proper or advisable under applicable laws and regulations to consummate and make effective the Exchange in the most expeditious manner practicable, including but not limited to the satisfaction of all conditions to the Exchange and seeking to remove promptly any injunction or other legal barrier that may prevent or delay such consummation. The parties agree to execute and deliver such documents, certificates, agreements and other writings and to take such other actions as may be reasonably necessary or desirable in order to consummate or implement expeditiously the Exchange.

Section 4.2. Certain Filings. The Company and each Management Investor shall cooperate with one another (i) in determining whether any action by or in respect of, or filing with, any governmental body, agency, official or authority is required, or any actions, consents, approvals or waivers are required to be obtained from parties to any material contracts, in connection with the consummation of the Exchange and (ii) in taking such actions or making any such filings, furnishing information required in connection therewith and seeking timely to obtain any such actions, consents, approvals or waivers.

ARTICLE 5

CONDITIONS TO EXCHANGE CLOSING

Section 5.1. Conditions to the Obligations of Each Party. The obligations of the Company and the Management Investors to consummate the Exchange are subject to the satisfaction of the following conditions:

(a) all of the conditions set forth in Article VI of the Merger Agreement shall have been either satisfied or waived;

(b) any required governmental and third party notices, authorizations, consents, orders or approvals shall have been obtained and be in effect;

- 5 -

(c) no court or governmental body, agency, or official shall have issued any order, and there shall not have been adopted or promulgated any statute, rule or regulation, that prohibits the consummation of the Exchange; and

(d) the conversion of the Company to a Delaware corporation shall have been completed.

Section 5.2. Conditions to Obligation of the Company. The obligation of the Company to consummate the Exchange Closing is subject to the satisfaction of the following further conditions:

(a) (i) each Management Investor shall have performed in all material respects all of his or her obligations hereunder required to be performed by him at or prior to the Closing (the “Closing Date”) and (ii) the representations and warranties of each Management Investor contained in this Agreement shall be true in all material respects at and as of the Closing Date as if made at and as of such time.

Section 5.3. Conditions to Obligations of Management Investors. The obligation of each Management Investor to transfer, assign, deliver and contribute to the Company, immediately prior to the Closing, all of each Management Investor’s respective Exchange Shares is subject to the satisfaction of the following further conditions:

(a) (i) the Company shall have performed in all material respects all of its obligations hereunder required to be performed by it at or prior to the Closing Date and (ii) the representations and warranties of the Company contained in this Agreement shall be true in all material respects at and as of the Closing Date as if made at and as of such time (except for representations and warranties made as of a specific date, which shall be true in all material respects at and as of such date); and

(b) the Management Investors shall have received a written undertaking from the Company to issue, at the Effective Time, to each Management Investor his or her respective New Shares.

ARTICLE 6

MISCELLANEOUS

Section 6.1. Notices. All notices provided for or permitted hereunder shall be made in writing by hand-delivery, registered or certified first-class mail, fax or reputable courier guaranteeing overnight delivery to the other party at the following addresses (or at such other address as shall be given in writing by any party to the others):

if to the Company, to:

Seitel Holdings, LLC

c/o ValueAct Capital Master Fund, L.P.

435 Pacific Avenue, 4^th Floor

San Francisco, CA 94133

- 6 -

Facsimile: (415)  ###-###-####

Attention: Allison Bennington, General Counsel

with a required copy to:

Dechert LLP

Cira Centre

2929 Arch Street

Philadelphia, PA 19104

Facsimile: (215)  ###-###-####

Attention: Christopher G. Karras

if to any of the Management Investors, to such Management Investor’s address as set forth on the signature page hereto or such other address as may be specified from time to time in writing to the Company by such Management Investor.

All such notices and other communications hereunder shall be in writing and shall be deemed to have been duly given if delivered personally, sent by telecopier (subject to electronic confirmation of such facsimile transmission and the sending (on the date of such facsimile transmission) of a confirmation copy of such facsimile by nationally recognized overnight courier service or by certified or registered mail, postage prepaid) or on the second business day after being sent by nationally recognized overnight courier service or on the fifth business day after being sent by registered or certified mail (postage prepaid, return receipt requested) to the respective party.

Section 6.2. Termination. (a) If the Merger Agreement is terminated in accordance with its terms, this Agreement will automatically terminate in its entirety.

(b) If this Agreement terminates pursuant to Section 6.2(a), this Agreement shall become void and of no effect with no liability on the part of any party (or any stockholder, director, officer, employee, agent, consultant or representative of such party) to any other party hereto, provided that no such termination shall relieve any party hereto of any liability or damages resulting from any willful breach by such party of this Agreement and provided, further that any Exchanges Shares delivered by Management Investors to the Company shall be returned promptly to the applicable Management Investors.

(c) Notwithstanding any other provision of this Agreement, if prior to the Effective Time a Management Investor is no longer an employee of Seitel (or any of its subsidiaries) for any reason, this Agreement shall become void and of no effect with regard to such Management Investor and any shares of Seitel Common Stock held by such Management Investor at the Effective Time shall be converted into the Merger Consideration (as defined in the Merger Agreement) at the Effective Time in accordance with the terms of the Merger Agreement and shall not be subject to Exchange under this Agreement.

Section 6.3. Specific Performance. The parties hereto agree that irreparable damage would occur in the event any provision of this Agreement is not performed in accordance with the terms hereof and that the parties shall be entitled to specific performance of the terms hereof; in addition to any other remedy at law or in equity.

- 7 -

Section 6.4. Entire Agreement. This Agreement constitutes the entire agreement between the parties, and supersedes all prior written and oral and all contemporaneous oral agreements and understandings, with respect to the subject matter hereof.

Section 6.5. Amendments and Waivers. Any provision of this Agreement may be amended or waived if, but only if; such amendment or waiver is in writing and is signed, in the case of an amendment, by each party hereto (provided, however, that in the event of a breach or default by one or more of the Management Investors hereunder, an amendment hereto need not be signed by such Management Investor to be effective if such Management Investor will no longer be a party to the Agreement after giving effect to such amendment), or in the case of a waiver, by the party against whom the waiver is to be effective. The Company will not amend this Agreement or waive any right or any condition to the obligations of the Company under this Agreement unless such action is approved by its Manager.

Section 6.6. Severability. If any term or other provision of this Agreement is invalid, illegal or incapable of being enforced by any rule of law or public policy, all other conditions and provisions of this Agreement shall nevertheless remain in full force and effect so long as the economic or legal substance of the Exchange is not affected in any manner materially adverse to any party. Upon such determination that any term or other provision is invalid, illegal or incapable of being enforced, the parties hereto shall negotiate in good faith to modify this Agreement so as to effect the original intent of the parties as closely as possible in an acceptable manner to the end that the Exchange is fulfilled to the extent possible.

Section 6.7. Governing Law. This Agreement shall be governed by and construed in accordance with the laws of the State of Delaware, regardless of the laws that might otherwise govern under principles of conflicts of law applicable hereto.

Section 6.8. Jurisdiction. Any suit, action or proceeding seeking to enforce any provision of; or based on any matter arising out of or in connection with, this Agreement or the Exchange shall be brought in any federal court in the State of Delaware, and each of the parties hereto hereby consents to the exclusive jurisdiction of such courts (and of the appropriate appellate courts therefrom) in any such suit, action or proceeding and irrevocably waives, to the fullest extent permitted by law, any objection that it may now or hereafter have to the laying of venue of any such suit, action or proceeding in any such court or that any such suit, action or proceeding brought in any such court has been brought in an inconvenient forum. Process in any such suit, action or proceeding may be served on any party anywhere in the world, whether within or without the jurisdiction of any such court. Without limiting the generality of the foregoing, each party hereto agrees that service of process upon such party as provided in Section 6.1 shall be deemed effective service of process upon such party.

Section 6.9. Waiver of Jury Trial. EACH OF THE PARTIES HERETO HEREBY IRREVOCABLY WAIVES ANY AND ALL RIGHT TO TRIAL BY JURY IN ANY LEGAL PROCEEDING ARISING OUT OF OR RELATED TO THIS AGREEMENT OR THE EXCHANGE.

- 8 -

Section 6.10. Costs and Expenses. All costs and expenses incurred in connection with this Agreement and the Exchange shall be paid by the party incurring such costs and expenses.

Section 6.11. Indemnification. The Company hereby indemnifies each Management Investor against and agrees to hold each such Management Investor harmless from any and all damages incurred or suffered by such Management Investor arising out of any misrepresentation or breach of warranty, covenant or agreement made or to be performed by the Company pursuant to this Agreement; provided, however, that the amount of damages for which the Company is required to indemnify any Management Investor pursuant hereto shall in no event exceed the number of Exchange Shares of such Management Investor listed on Schedule II hereto multiplied by $3.70. Each Management Investor hereby indemnifies the Company against and agrees to hold it harmless from any and all damages incurred or suffered by the Company arising out of any misrepresentation or breach of warranty, covenant or agreement made or to be performed by such Management Investor pursuant to this Agreement; provided, however, that the amount of damages for which any Management Investor is required to indemnify the Company pursuant hereto shall in no event exceed the number of Exchange Shares of such Management Investor listed on Schedule II hereto multiplied by $3.70.

Section 6.12. Survival of Representations and Warranties. The representations and warranties of each party contained in this Agreement shall survive the Closing.

Section 6.13. Descriptive Headings; Definitions. The descriptive 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. The definitions contained in this Agreement are applicable to the singular as well as the plural forms of such terms and to the masculine as well as to the feminine and neuter genders of such terms.

Section 6.14. Counterparts. This Agreement may be executed in counterparts, each of which shall be deemed to be an original, but all of which shall constitute one and the same agreement.

Section 6.15. Successors and Assigns. The provisions of this Agreement shall be binding upon and inure to the benefit of the parties hereto and their respective successors and assigns, provided that no party may assign, delegate or otherwise transfer any of its rights or obligations under this Agreement without the consent of the other parties hereto.

Section 6.16. Parties in Interest. This Agreement shall be binding upon and inure solely to the benefit of each party hereto, and nothing in this Agreement, express or implied, is intended to or shall confer upon any other person any right, benefit or remedy of any nature whatsoever under or by reason of this Agreement.

- 9 -

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

- 10 -

MANAGEMENT INVESTORS

(continued)

- 11 -

MANAGEMENT INVESTORS

(continued)

- 12 -

Exhibit 10.4

Schedule I

Shares of Common Stock Owned by Management Investors

-13-

Schedule II

Shares of Seitel Common Stock to be Exchanged by Management Investors for New Shares

of Company Common Stock

- 14 -

Exhibit A

Certificate of Incorporation

- 15 -