COMMON STOCK PURCHASE AGREEMENT

Exhibit 10.1

C OMMON S TOCK P URCHASE A GREEMENT

THIS COMMON STOCK PURCHASE AGREEMENT (this “ Agreement ”) is made and entered into effective as of May 22, 2009, by and among ODYSSEY MARINE EXPLORATION, INC. , a Nevada corporation (the “ Company ”), and the investor(s) listed on the counterpart signature page(s) hereto, each of which is herein individually referred to as an “ Investor ” and all of which are herein collectively referred to as the “ Investors .”

Background Information:

The Company proposes to issue and sell to the Investors, and the Investors propose to purchase and accept from the Company, up to an aggregate of 1,720,000 shares (the “ Shares ”) of the Company’s common stock, par value $0.0001 per share (the “ Common Stock ”). The purpose of this Agreement is to set forth the terms and conditions upon which the Company will issue and sell the Shares to the Investors and the Investors will purchase the Shares from the Company, as well as certain other related matters.

NOW, THEREFORE, in consideration of the foregoing recitals and the terms, conditions, and provisions hereof, the parties hereto, intending to be legally bound hereby, agree as follows:

Article 1

Purchase and Sale of Shares

Section 1.1 Sale and Issuance of Shares.

(a) On or prior to the Closing (as defined below), the Company shall have authorized the sale and issuance to the Investors of the Shares.

(b) Subject to the terms and conditions of this Agreement, each Investor agrees to purchase at the Closing, and the Company agrees to sell and issue to each Investor at the Closing, that number of Shares set forth below, such Investor’s name on such Investor’s counterpart signature page hereto for $2.965 per share (the “ Purchase Price ”),

Section 1.2 Closing. The consummation of purchase and sale of the Shares (the “ Closing ”) shall take place at the offices of the Company, located at 5215 West Laurel Street, Tampa, Florida, on May 22, 2009, or at such other time and place as the Company and the Investors acquiring in the aggregate a majority of the Shares sold pursuant to this Agreement agree upon orally or in writing (as applicable, the “ Closing Date ”). At the Closing, or as soon as practicable thereafter, the Company shall deliver to each Investor a certificate representing the Shares that such Investor is purchasing or acquiring against payment of the purchase price therefore by check, wire transfer, or any combination thereof. Payment by official bank check may be delivered to Odyssey Marine Exploration, Inc., 5215 West Laurel Street, Tampa, Florida 33607, or payment may be made by wire transfer of immediately available funds to:

1

Article 2

Representations and Warranties

of the Company

The Company hereby represents and warrants to the Investors as follows:

Section 2.1 Organization. The Company is duly organized, validly existing, and in good standing under the laws of the State of Nevada. The Company and each of its Subsidiaries (as defined in Rule 405 under the Securities Act of 1933, as amended (the “ Securities Act ”)) has full power and authority to own, operate and occupy its properties and to conduct its business as presently conducted and as described in the documents filed by the Company under the Securities Exchange Act of 1934, as amended (the “ Exchange Act ”), including, without limitation, the Company’s Annual Report on Form 10-K for the fiscal year ended December 31, 2008, the Company’s Quarterly Report on Form 10-Q for the quarterly period ended March 31, 2009, the Company’s Proxy Statement on Schedule 14A for the Annual Meeting of Shareholders held May 27, 2009, and the Company’s Current Reports on Form 8-K, since January 1, 2009 (collectively, the “ Exchange Act Documents ”), and is registered or qualified to do business and in good standing in each jurisdiction in which the nature of the business conducted by it or the location of the properties owned or leased by it requires such qualification and where the failure to be so qualified would have a material adverse effect upon the condition (financial or otherwise), earnings, business or business prospects, properties or operations of the Company and its Subsidiaries, considered as one enterprise (a “ Material Adverse Effect ”), and no proceeding has been instituted in any such jurisdiction revoking, limiting or curtailing, or seeking to revoke, limit or curtail, such power and authority or qualification.

Section 2.2 Due Authorization and Valid Issuance. The Company has all requisite corporate power and authority to execute, deliver and perform its obligations under this Agreement, and this Agreement has been duly authorized and validly executed and delivered by the Company and constitutes a legal, valid and binding agreement of the Company, enforceable against the Company in accordance with its terms, except as rights to indemnity and contribution may be limited by state or federal securities laws or the public policy underlying such laws, except as enforceability may be limited by applicable bankruptcy, insolvency, reorganization, moratorium or similar laws affecting creditors’ and contracting parties’ rights generally, and except as enforceability may be subject to general principles of equity (regardless of whether such enforceability is considered in a proceeding in equity or at law). The Shares have been duly authorized and, upon issuance in accordance with the terms of this Agreement, shall be validly issued and free from all taxes, liens and charges with respect to the issue thereof, and the Shares shall be fully paid and nonassessable.

Section 2.3 Non-Contravention. The execution and delivery of this Agreement, the issuance and sale of the Shares under this Agreement, the fulfillment of the terms of this Agreement and the consummation of the transactions contemplated hereby will not (a) conflict with or constitute a violation of, or default (with the passage of time or otherwise) under, (i) any material bond, debenture, note or other evidence of indebtedness, lease, contract, indenture, mortgage, deed of trust, loan agreement, joint venture or other agreement or instrument to which the Company or any Subsidiary is a party or by which it or any of its Subsidiaries or their respective properties are bound, (ii) the articles of incorporation, bylaws or other organizational documents of the Company or any Subsidiary, or (iii) any law, administrative regulation, ordinance or order of any court or governmental agency, arbitration panel or authority applicable to the Company or any Subsidiary or their respective properties, except in the case of clauses (i) and (iii) for any such conflicts, violations or defaults which are not reasonably likely to have a Material Adverse Effect, or (b) result in the creation or imposition of any lien, encumbrance, claim, security interest or restriction whatsoever upon any of the material properties or assets of the Company or any Subsidiary or an acceleration of indebtedness pursuant to any obligation, agreement or condition contained in any material bond, debenture, note or any other evidence of indebtedness or any material indenture, mortgage, deed of trust or any other agreement or instrument to which the Company or any Subsidiary is a party or by which any of them is bound or to which any of the material property or assets

2

of the Company or any Subsidiary is subject. No consent, approval, authorization or other order of, or registration, qualification or filing with, any regulatory body, administrative agency, or other governmental body in the United States or any other person is required for the execution and delivery of this Agreement and the valid issuance and sale of the Shares to be sold pursuant to this Agreement, other than such as have been made or obtained, and except for any post-closing securities filings or notifications required to be made under federal or state securities laws or under the rules of The NASDAQ Stock Market.

Section 2.4 Capitalization. As of the date of this Agreement, the authorized capital stock of the Company consists of (a) 100,000,000 shares of Common Stock, of which as of the date of this Agreement, 53,164,994 shares are issued and outstanding, 4,782,779 shares are reserved for issuance pursuant to the Company’s employee incentive plan or plans, and 7,747,600 shares are reserved for issuance pursuant to securities exercisable or exchangeable for, or convertible into, shares of Common Stock, and (b) 9,810,000 shares of preferred stock, of which (i) 7,340,000 shares have been designated as Series D Shares, of which 6,347,600 shares are issued and outstanding as of the date of this Agreement, and (ii) 20 shares have been designated as Series E Shares, of which 13 shares are issued and outstanding as of the date of this Agreement. All of such outstanding shares have been, or upon issuance will be, validly issued and are fully paid and nonassessable. Except as disclosed in the Exchange Act Documents: (a) no shares of the Company’s capital stock are subject to preemptive rights or any other similar rights or any liens or encumbrances suffered or permitted by the Company; (b) there are no outstanding options, warrants, scrip, rights to subscribe to, calls or commitments of any character whatsoever relating to, or securities or rights convertible into, or exercisable or exchangeable for, any shares of capital stock of the Company or any of its Subsidiaries, or contracts, commitments, understandings or arrangements by which the Company or any of its Subsidiaries is or may become bound to issue additional shares of capital stock of the Company or any of its Subsidiaries or options, warrants, scrip, rights to subscribe to, calls or commitments of any character whatsoever relating to, or securities or rights convertible into, or exercisable or exchangeable for, any shares of capital stock of the Company or any of its Subsidiaries; (c) there are no outstanding debt securities, notes, credit agreements, credit facilities or other agreements, documents or instruments evidencing indebtedness of the Company or any of its Subsidiaries or by which the Company or any of its Subsidiaries is or may become bound; (d) there are no agreements or arrangements under which the Company or any of its Subsidiaries is obligated to register the sale of any of their securities under the Securities Act except pursuant to this Agreement; (e) there are no outstanding securities or instruments of the Company or any of its Subsidiaries that contain any redemption or similar provisions, and there are no contracts, commitments, understandings or arrangements by which the Company or any of its Subsidiaries is or may become bound to redeem a security of the Company or any of its Subsidiaries; (f) there are no securities or instruments containing anti-dilution or similar provisions that will be triggered by the issuance of the Shares; (g) the Company does not have any stock appreciation rights or “phantom stock” plans or agreements or any similar plan or agreement; and (h) the Company and its Subsidiaries have no liabilities or obligations required to be disclosed in the Exchange Act Documents but not so disclosed in the Exchange Act Documents, other than those incurred in the ordinary course of the Company’s or any Subsidiary’s respective businesses and which, individually or in the aggregate, do not or would not have a Material Adverse Effect.

Section 2.5 Legal Proceedings. There is no material legal or governmental proceeding pending or, to the knowledge of the Company, threatened to which the Company or any Subsidiary is or may be a party or of which the business or property of the Company or any Subsidiary is subject that is not disclosed in the Exchange Act Documents.

Section 2.6 No Violations. Neither the Company nor any Subsidiary is in violation of its articles of incorporation, bylaws, or other organizational document, or in violation of any law, administrative regulation, ordinance or order of any court or governmental agency, arbitration panel or authority applicable to the Company or any Subsidiary, which violation, individually or in the aggregate, would be reasonably likely to have a Material Adverse Effect, or is in default (and there exists no condition which, with the passage of time or otherwise, would constitute a default) in any material respect in the

3

performance of any bond, debenture, note or any other evidence of indebtedness in any indenture, mortgage, deed of trust or any other material agreement or instrument to which the Company or any Subsidiary is a party or by which the Company or any Subsidiary is bound or by which the properties of the Company or any Subsidiary are bound, which would be reasonably likely to have a Material Adverse Effect.

Section 2.7 Governmental Permits, Etc. With the exception of the matters which are dealt with separately in Sections 2.1, 2.12, 2.13, and 2.14, each of the Company and its Subsidiaries has all necessary franchises, licenses, certificates and other authorizations from any foreign, federal, state or local government or governmental agency, department, or body that are currently necessary for the operation of the business of the Company and its Subsidiaries as currently conducted and as described in the Exchange Act Documents, except where the failure to currently possess such franchises, licenses, certificates or other authorizations would not reasonably be expected to have a Material Adverse Effect.

Section 2.8 Intellectual Property. Except as specifically disclosed in the Exchange Act Documents (a) each of the Company and its Subsidiaries owns or possesses sufficient rights to use all material patents, patent rights, trademarks, copyrights, licenses, inventions, trade secrets, trade names and know-how (collectively, “ Intellectual Property ”) described or referred to in the Exchange Act Documents as owned or possessed by it or that are necessary for the conduct of its business as now conducted or as proposed to be conducted as described in the Exchange Act Documents except where the failure to currently own or possess such rights would not have a Material Adverse Effect, (b) neither the Company nor any of its Subsidiaries is infringing, or has received any notice of, or has any knowledge of, any asserted infringement by the Company or any of its Subsidiaries of, any rights of a third party with respect to any Intellectual Property that, individually or in the aggregate, would have a Material Adverse Effect and (c) neither the Company nor any of its Subsidiaries has received any notice of, or has any knowledge of, infringement by a third party with respect to any Intellectual Property rights of the Company or of any Subsidiary that, individually or in the aggregate, would have a Material Adverse Effect.

Section 2.9 Exchange Act Documents; Financial Statements. As of their respective dates, the Exchange Act Documents complied in all material respects with the requirements of the Exchange Act and the rules and regulations of United States Securities and Exchange Commission (the “ SEC ”) promulgated thereunder applicable to the Exchange Act Documents, and none of the Exchange Act Documents, at the time they were filed or are to be filed with the SEC, contained or will contain any untrue statement of a material fact or omitted to state a material fact required to be stated therein or necessary in order to make the statements therein, in the light of the circumstances under which they were made, not misleading. The financial statements of the Company and the related notes contained in the Exchange Act Documents present fairly in all material respects, in accordance with generally accepted accounting principles, the financial position of the Company and its Subsidiaries as of the dates indicated, and the results of its operations and cash flows for the periods therein specified consistent with the books and records of the Company and its Subsidiaries. Such financial statements (including the related notes) have been prepared in accordance with generally accepted accounting principles applied on a consistent basis throughout the periods therein specified, except as may be disclosed in the notes to such financial statements, and except as disclosed in the Exchange Act Documents. The other financial information contained in the Exchange Act Documents has been prepared on a basis consistent with the financial statements of the Company.

Section 2.10 No Material Adverse Change. Except as disclosed in the Exchange Act Documents, since December 31, 2008, there has not been (a) any material adverse change in the financial condition of the Company and its Subsidiaries considered as one enterprise, (b) any material adverse event affecting the Company or its Subsidiaries, (c) any obligation, direct or contingent, that is material to the Company and its Subsidiaries considered as one enterprise, incurred by the Company, except obligations incurred in the ordinary course of business, (d) any dividend or distribution of any kind declared, paid or made on the capital stock of the Company or any of its Subsidiaries, or (e) any loss or damage (whether or not insured) to the physical property of the Company or any of its Subsidiaries which has been sustained which has had a Material Adverse Effect.

4

Section 2.11 NASDAQ Stock Market Compliance. The Common Stock is registered pursuant to Section 12(b) or Section 12(g) of the Exchange Act and is listed or quoted on the NASDAQ Capital Market (the “ Principal Market ”), and the Company has taken no action designed to, or likely to have the effect of, terminating the registration of the Common Stock under the Exchange Act or de-listing the Common Stock from the Principal Market, nor, except as disclosed in the Exchange Act Documents, has the Company received any notification that the SEC or the Principal Market is contemplating terminating such registration or listing.

Section 2.12 Reporting Status. The Company has filed in a timely manner all documents that the Company was required to file under the Exchange Act during the 12 months preceding the date of this Agreement. And, until the date on which all of the Shares have been sold pursuant to a registration statement, or Rule 144, the Company will use its commercially reasonable efforts to file with the SEC all reports it is required to file under the Exchange Act.

Section 2.13 Listing. The Company shall comply with all requirements of the Principal Market with respect to the issuance and listing of the Shares on the Principal Market.

Section 2.14 No Manipulation of Stock. The Company has not taken and will not, in violation of applicable law, take any action designed to or that would reasonably be expected to cause or result in stabilization or manipulation of the price of the Common Stock to facilitate the sale or resale of the Shares.

Section 2.15 Company not an “Investment Company.” The Company has been advised of the rules and requirements under the Investment Company Act of 1940, as amended (the “ Investment Company Act ”). The Company is not, and immediately after receipt of payment for the Shares will not be, an “investment company” or an entity “controlled” by an “investment company” within the meaning of the Investment Company Act and shall conduct its business in a manner so that it will not become subject to the Investment Company Act.

Section 2.16 Foreign Corrupt Practices. Neither the Company nor, to the knowledge of the Company, any agent or other person acting on behalf of the Company has (a) directly or indirectly, used any corrupt funds for unlawful contributions, gifts, entertainment or other unlawful expenses related to foreign or domestic political activity, (b) made any unlawful payment to foreign or domestic government officials or employees or to any foreign or domestic political parties or campaigns from corporate funds, (c) failed to disclose fully any contribution made by the Company (or made by any person acting on its behalf of which the Company is aware) which is in violation of law, or (d) violated in any material respect any provision of the Foreign Corrupt Practices Act of 1977, as amended.

Section 2.17 Contracts. The contracts described in the Exchange Act Documents that are material to the Company are in full force and effect on the date of this Agreement, and neither the Company nor, to the Company’s knowledge, any other party to such contracts is in breach of or default under any of such contracts which would have a Material Adverse Effect.

Section 2.18 Taxes. The Company has filed all necessary federal, state and foreign income and franchise tax returns and has paid or accrued all taxes