Exhibit 10.4

Case No. FF–G–017B

SECURITY AGREEMENT

This Security Agreement (hereinafter, the “Agreement”), made between Omega Protein, Inc., (hereinafter, the “Borrower”), whose address is 2105 City West Blvd., Suite 500, Houston, Texas 77042 and the UNITED STATES OF AMERICA, acting by and through the Secretary of Commerce, National Oceanic and Atmospheric Administration, National Marine Fisheries Service, Financial Services Division, 1315 East-West Highway, Silver Spring, Maryland 20910, which is the Secured Party, (hereinafter the “Government”).

All terms contained herein are defined in the Acknowledgment of Definitions executed by all parties to this transaction.

W I T N E S S E T  H

WHEREAS, the Borrower desires to enter into a promissory Note to the United States (hereinafter, the “Note”), dated May 25, 2010, in the amount of TEN MILLION AND 00/100 Dollars ($10,000,000.00), pursuant to the provisions of Title XI of the Merchant Marine Act, 1936, as amended, found at 46 USC § 1271 et seq., and 50 CFR 253, as amended by Public Law 104-297 on October 11, 1996, known as the Fisheries Finance Program, (hereinafter, the “FFP Debt”); and

WHEREAS, the Government will not enter into this transaction unless the Government is granted a security interest in certain property.

NOW THEREFORE, in consideration of the premises and other good and valuable consideration, the receipt whereof being hereby acknowledged, the parties agree as follows:

Section 1. The Borrower hereby grants to the Government a security interest in the following described property, together with all accessories, substitutions, additions, replacements, parts and accessions affixed to or used in connection therewith (hereinafter, the “Collateral”):

(a) The whole of the fishing vessel GRAND CHENIERE, Official Number 590692, together with all related gear, boilers, machinery, electronics, equipment, motors, skiffs, inventory, supplies, contracts, contract rights, charter hire, freight, licenses and/or permits, general intangibles, transferable fishery conservation and management allocations, now owned or hereafter acquired, attached or not attached or to be attached, to secure payment of the Borrower’s debt to the Government as evidenced hereby and by Borrower’s Note to the Government of even date herewith payable to the Government, in

1

accordance with the Note, in the amount of TEN MILLION AND NO/Dollars, ($10,000,000.00) payable on the terms, at the times, and with interest as set forth in said Note. Borrower agrees to pay the Note and, if any portion thereof, principal or interest, is not paid when due, Borrower agrees to pay, in addition to the foregoing, the reasonable collection costs of the Government;

(b) Any and all federal or state fisheries permits, individual fishing quotas (IFQ), individual transferable quotas (ITQ), community development quotas (CDQ), quota shares, allocations, endorsements, rights, licenses, or tags, whether vested individually with the Borrower or appurtenant to the Vessel, whether now owned or hereafter acquired, whether now existing or hereafter created by rule, regulation, statute or fishery management council action, which now exist or are hereafter created pursuant to any limited entry programs, moratorium periods, high seas permits, license limitation programs or total allowable catch and domestic annual processing assessments or like programs or assessments whether or not any of the foregoing relate to or affect the fishing operations of the vessel.

(c) All insurances pertaining to the Collateral, including, without limitation, hull and machinery, increased value, war risk, protection and indemnity, pollution, worker’s liability and compensation, loss of earnings, personal property, liability and all other insurances and association entries, and all claims and all returns of premiums, dues, calls, and assessments that are not immediately applied to future premiums, dues, calls, and assessments, and all other sums or claims for sums due or to become due thereunder;

(d) All debts and obligations owing to the Borrower, including, without limitation, interest thereon, charges and other expenses and fees advanced by or incurred by or for the Government, and all liens and encumbrances securing any or all of the foregoing;

(e) Borrower grants the Government a security interest in the following real estate situated in Northumberland County, Commonwealth of Virginia, fully described in Exhibit A.

EXHIBIT “A” IS ATTACHED AND MADE A PART HEREOF

together with all buildings and other improvements, hereditaments and appurtenances thereunto belonging, or in any wise appertaining now existing or hereafter erected upon the premises and all the income and rents arising therefrom. Borrower does hereby intend to convey and does convey all of Borrower’s right, title and interest in and to any strips and gores Borrower may now own contiguous to the above described property;

(f) It is expressly understood and agreed, as a part of the consideration for the loan made to the Borrower and secured by the

2

premises described in Exhibit A, this instrument covers and includes all surface, subsurface and/or mineral estate ownership now or after acquired by the undersigned in the above property and whether or not expressly excepted from the description to the above security premises, any provisions herein to the contrary being of no force and effect;

(g) For the consideration aforesaid, and as further security for any and all debt(s) and obligation(s) described above, said Borrower does hereby assign, pledge and transfer to the Government, and grant to the Government a security interest in and to the following described property and interests which are listed on Exhibit B and/or set out as follows: (1) all timber of all kind, character and description planted and/or growing, or to be planted and/or grown, on the hereinabove described property; (2) all crop allotments, quotas, and/or (3) all rents, profits, issues, income, royalties, bonuses, and revenue of said property, or any part or interest herein, from time to time accruing whether under leases or tenancies now existing or hereafter created; (4) each and every policy of hazard insurance, or the like, now or hereafter in effect which insures said property or any building, fixture and/or improvement thereon, or any part thereof, together with all the right, title and interest of Borrower in and to such policy, including but not limited to any premiums paid (or rights to return premiums) and/or all proceeds or payments thereunder; (5) all judgments, award of damages and settlements hereafter made resulting from condemnation proceedings or the taking of the real property, or any part thereof, under the power of eminent domain, or for any damage (whether caused by such taking or otherwise) to the property, or any part thereof, or to any rights appurtenant thereto; (6) all building materials, equipment, fixtures and fittings of all kind, character, and description used in connection with or relating to said property and/or buildings, fixtures or improvements thereon; (7) all equipment, including, but not limited to: forklifts, bobcats, cranes, pallet trucks, lift trucks and other product or material movement equipment of whatsoever nature; all trailers, tanks, trucks or other rolling stock of whatsoever nature except that equipment used for transport and licensed by the state motor vehicle department; all fish unloading, transfer and conveying equipment of whatsoever nature; fungible goods, including fish; all fish processing equipment of whatsoever nature; all fish weighing equipment of whatsoever nature; all cooling, refrigerating, freezing and other fish holding equipment (blast freezers, coolers, or other refrigeration equipment) of whatsoever nature; all fish packaging equipment of whatsoever nature; all fish baskets, totes, tanks, tubs and other fish holding equipment of whatsoever nature; all ice makers of whatsoever nature, all hand and power tools of whatsoever nature; all office equipment of whatsoever nature; all fish hatching, releasing, rearing, growing, tending and other equipment of whatsoever nature in any way associated with fisheries cultivation of every sort—all together with all associated equipment, machinery, parts, tools, or other items of

3

whatsoever nature and whether fixed or unfixed to the property or any other premises whatsoever; and/or (8) all tangible or intangible property found on the premises which is not listed on Exhibit “B”, and products, proceeds, and additions and/or replacements of any or all of the property described above in Items 1 through 7, also including all after-acquired personal property to be located in or about the said facility of Borrower, subject to any purchase-money security interest acquired by any vendor of said after-acquired personal property;

EXHIBIT “B” IS ATTACHED AND MADE A PART HEREOF

Section 2. The Borrower hereby warrants and covenants that:

(a) Except as may otherwise be required in the ordinary course of business, at all times the items listed on Exhibit B will be kept on the property itself, in transit, or in storage and shall not be removed from said location, in whole or in part, until such time as written consent to a change of location is obtained by the Borrower from the Government;

(b) The Collateral is to be used primarily for business use and kept at the Borrower’s principal place of business.

Section 3. Other terms and conditions:

(a) In the event that this Security Agreement, the Note, or any provisions hereof or thereof shall be deemed invalid in whole or in part by reason of any present or future law of the United States or any decision of any authoritative court, or if the documents at any time held by the Government be deemed by the Government, for any reason, insufficient to carry out the true intent and spirit of this Security Agreement and the Note, then, from time to time, the Borrower will execute on its own behalf such other and further assurances and documents as in the opinion of counsel for the Government may be required to more effectually subject the Collateral to the payment of the principal sum of the Note, together with interest thereon, as in the Note and as herein provided, and in the performance of the terms and conditions of the Note and this Security Agreement. Upon failure of the Borrower so to do, the Government may execute such other and further assurances and documents, for and in the name of the Borrower, and the Borrower hereby irrevocably appoints the Government the agent attorney-in-fact of the Borrower so to do. Any expenses of the Government in connection with the foregoing shall be a debt due from the Borrower to the Government in payment thereof and shall be added to the outstanding principal amount and be secured by the lien of this Security Agreement;

(b) The Borrower will faithfully observe, perform and discharge all of the covenants, conditions, and obligations which are imposed on the Borrower by any and all indentures and other agreements or

4

documents and will not permit to occur any act or omission which is or may be declared to be a default under any such indenture, agreement, or document;

Section 4. The Borrower hereby further warrants and covenants that:

(a) No financing statement covering any of the Collateral described herein is on file in any public office except in favor of the Government. The Borrower is the owner of the Collateral free from any prior lien, security interest or encumbrance, except in favor of the Government, and will defend the Collateral against the claims and demands of all persons whomsoever;

(b) Except as may otherwise be required in the ordinary course of business, the Borrower will not sell, exchange, lease, or otherwise dispose of the Collateral, or any part thereof, or suffer or permit any lien, levy, or attachment, or security interest therein, or financing statement to be filed with reference thereto, other than that of the Government;

(c) The Borrower will maintain the Collateral in good condition and repair and preserve the same against waste, loss, damage, or depreciation in value other than by reasonable wear. The Borrower will not use any of the Collateral in violation of any law or public regulation. The Government may examine and inspect the Collateral at any reasonable times, wherever located, and for that purpose hereby is authorized by the Borrower to enter any place or places where the Collateral may be;

(d) The Borrower will keep the Collateral fully insured against loss or damage by fire, theft (and collision if applicable), and such other hazards as the Government may from time to time require, with such deductible provisions, upon such terms, including loss payable and other endorsements, and in such company or companies as the Government may approve; Borrower immediately will deliver all policies to the Government, to be retained by the latter in pledge to secure Borrower’s obligations hereunder, with irrevocable authority to adjust any loss, receive and receipt for any sum payable, surrender any policy, discharge and release any insurer, endorse in Borrower’s name any loss or refund check or draft and, in general, exercise in the name of the Borrower or otherwise, any and all rights of the Borrower in respect thereto or in respect to the proceeds thereof;

(e) The Borrower will pay, when due, all taxes, license fees and assessments relative to the Collateral or its use and relative to the Note. Should the Borrower fail in its performance of any of the foregoing, the Government may pay the same, including any security interest having priority hereto, may order and pay for the repair, maintenance and preservation of the Collateral, or any part thereof, may place and pay for any such insurance and may pay any such taxes.

5

The Borrower agrees to pay to the Government on demand all of the latter’s disbursements for any of said purposes with interest at the rate of eighteen percent (18%) per annum, or such lesser rate which the Government, in its sole discretion, may determine. Said sum shall be added to the sums due under the Note, shall be an indebtedness of the Borrower, immediately due and payable, and shall be secured by this Security Agreement.

Notwithstanding the Government’s election under this provision to fix an interest rate of less than eighteen percent (18%) for payment of these items, in the event of a default which results in acceleration of sums due under the Note, the accelerated interest rate of eighteen percent (18%), will also be applied to any amounts expended for items listed in this paragraph, from the date of payment until repaid;

(f) The Borrower agrees to notify the Government promptly in writing of any change in its business name or address, corporate structure (including the jurisdiction under which it is incorporated), principal place of business and Borrower’s residence.

(g) By executing this Security Agreement, the Borrower authorizes the Government to file financing statements and amendments thereto to perfect the security interests created by this Agreement. The recording of these financing statements will be at the Borrower’s expense.

(h) The Borrower hereby consents to any extension of time of payment and to any substitution, exchange, or release of Collateral and to the addition to or release of any party or person primarily or secondarily liable for the Note.

Section 5. General terms:

(a) The Note is a separate instrument and may be negotiated, extended, or renewed by the Government without releasing the Borrower, and and all Collateral, or any guarantor or co-maker;

(b) All of the benefits of this Security Agreement shall inure to the Government, its successor in interest and assigns, and the obligations hereunder shall be binding upon the Borrower, its legal representatives, successors and assigns;

(c) If there is more than one Borrower or guarantor or co-maker of the Note, the obligation of each and all shall be primary and joint and several;

(d) The provisions of this Security Agreement are severable, if a provision is held invalid or unenforceable by a court of competent jurisdiction, such holding shall not affect or impair any of the remaining provisions;

6

(e) The Government shall not be deemed to have waived any of its rights under this or any other agreement executed by the Borrower unless the waiver is in writing signed by the Government. No delay in exercising the Government’s rights shall constitute a waiver nor shall a waiver on one occasion operate as a waiver of such right on a future occasion;

(f) Each notice from one to the other party in this Security Agreement shall be sufficient if served personally or given by U. S. registered or certified mail, addressed to the other party at its last known address. Reasonable notice, when notice is required, shall be deemed to be five days from date of mailing;

Section 6. Default:

(a) The Borrower shall be in default under this Security Agreement upon the happening of any of the following events or conditions:

(1) The Borrower’s failure to pay, when due, the principal of or interest on the Note, including any amendments thereto or substitutions therefore, and/or any other amounts due the Government in connection with this transaction;

(2) The Borrower’s failure to keep, observe, or perform any provision of this Security Agreement or any other agreement between the Borrower and the Government, including but not limited to, the Preferred Ship Mortgage on the aforementioned fishing vessel, and the Deed of Trust on the aforementioned real property, and all loan documents;

(3) The failure of any guarantor, co-maker, or other party to keep, observe or perform any agreement between said party and the Government connected with or arising from the aforementioned obligation;

(4) The discovery of any misrepresentation, or material falsity of any warrant, representation, or statement made or furnished by the Borrower to the Government, whether or not in connection with this Security Agreement;

(5) The loss, theft, or destruction of or substantial damage to the Collateral;

(6) The Government deems or has reasonable cause to deem itself insecure;

7

(7) The failure or termination of the business, or commencement of any insolvency or receivership proceedings by or against the Borrower, or if the Borrower dies or becomes insolvent, and if Borrower is a partnership, the death of any partner, and if the Borrower is a corporation, the dissolution of said corporation;

(8) The occurrence of any event that would adversely affect the ability of the Borrower or the Guarantor to timely service the debt owed the Government or that would cause the Government to reasonably deem itself an insecure creditor.

Section 7. Cure of Defaults:

If the Borrower shall have, within fifteen (15) days after the occurrence thereof, removed and remedied each event of default as set forth herein, then in every such case, the Secretary shall waive any such event of default; but no such waiver shall extend to nor affect any subsequent or other event of default nor impair any rights or remedies consequent thereon.

Section 8. Remedies of the Government:

Upon Borrower’s default, the Government shall have each and all of the rights and remedies granted to him by the Uniform Commercial Code of the state in which this Security Agreement is filed, by the Note, by this Security Agreement, and by the Preferred Ship Mortgage, by the Deed of Trust, and other loan documents, and may declare the Note immediately due and payable and thereafter shall bear interest at eighteen percent (18%) per annum, unless limited by applicable state law, and may require the Borrower to assemble the Collateral and make it available to the Government at a place to be designated by the Government which is reasonably convenient to both parties. The Borrower agrees to pay the Government’s reasonable counsel fees and other expenses incurred by the latter in retaking, holding, preparing for sale, and realizing on said Collateral. Should suit or action be instituted on this Security Agreement, on the Note, or to replevy the Collateral, or any part thereof, Borrower agrees to pay (1) the Government’s reasonable attorney’s fees to be fixed by the trial court and (2) on appeal, if any, similar fees in the appellate court. Provided, however, that if the Borrower shall have removed and remedied each Event of Default within fifteen (15) days after the occurrence thereof, then in every such case the Government shall waive any such Event of Default; but no such waiver shall extend to nor affect any subsequent or other Event of Default nor impair any rights or remedies consequent thereon; and provided further that if at any time after the expiration of fifteen (15) days after any Event of Default shall have occurred, all Events of Default shall have been remedied and removed and full performance made by the Borrower to the satisfaction of the Government and all installments of principal and interest in arrears (including interest at

8

the default rate, as aforesaid) and the reasonable charges and expenses, if any, of the Government, its agents and attorneys, shall have been paid, then and in every such case the Government may waive any such Event of Default; and provided, also, that no waiver hereunder shall extend to nor affect any subsequent or other Event of Default nor impair any rights or remedies consequent thereon.

Section 9. Governing Law:

Except to the extent that the laws of the United States govern, all provisions of this Agreement shall be construed, given effect, and enforced according to the laws of the Commonwealth of Virginia. With respect to any claim or proceeding related to this Agreement the Borrower hereby consents to and subjects itself to the jurisdiction of the federal court of competent jurisdiction of the Commonwealth of Virginia and agrees that the venue of any action or proceeding relating to this Agreement shall be exclusively in the federal court situated in the Commonwealth of Virginia unless the Secretary has instituted proceedings where the Collateral may be found and in such case, Borrower consents to and subjects itself to the jurisdiction of the federal court which maintains jurisdiction over the Collateral.

IN WITNESS WHEREOF, the parties have executed and delivered this Security Agreement as of the     day of ,             2010.

9

10

ACKNOWLEDGMENT

On the    day of             , 2010, before me personally came Shawn Barry to me known and known to me to be the duly authorized representative of the Secretary of Commerce of the United States of America and he duly acknowledged to me that he executed the above instrument as such representative of the Secretary of Commerce pursuant to the authority vested in him by the laws of the United States.

11

ACKNOWLEDGMENT

On the 25^th day of May, 2010 before me personally appeared Robert W. Stockton, to me known or produced satisfactory identification, who being duly sworn, did depose and say that he is the Vice President and Treasurer of Omega Protein, Inc., and that he signed his name to said Security Agreement by like order, and acknowledged that the same is the free and voluntary act and deed of said corporation and of himself as such Vice President and Treasurer for the uses and purposes therein expressed.

/s/ Michelle Morton Reese

Notary Public

12