Exhibit 5.1

[FRIED, FRANK, HARRIS, SHRIVER & JACOBSON LLP LETTERHEAD]

July 20, 2012

Navios Maritime Holdings Inc.

85 Akti Miaouli Street

Piraeus, Greece 185 38

Ladies and Gentlemen:

We are acting as special United States and New York counsel to Navios Maritime Holdings Inc., a Marshall Islands corporation (the “Issuer”), Navios Maritime Finance (US) Inc., a Delaware corporation (the “Co-Issuer” and, together with the Issuer, the “Issuers”) and certain of the Issuer’s subsidiaries listed on Exhibit A hereto (each, a “Guarantor”), in connection with a Registration Statement on Form F-4 (the “Registration Statement”) filed with the Securities and Exchange Commission under the Securities Act of 1933, as amended (the “Securities Act”), relating to the proposed offer to exchange up to $88,000,000 in aggregate principal amount of new 8 7/8% First Priority Ship Mortgage Notes due 2017 (the “Exchange Notes”), which are being registered under the Securities Act, for a like principal amount of the Co-Issuers’ issued and outstanding 8 7/8% First Priority Ship Mortgage Notes due 2017 (the “Outstanding Notes”). The Outstanding Notes and the Exchange Notes are collectively referred to herein as the “Notes.” Pursuant to the Indenture (as defined below), the Outstanding Notes are, and the Exchange Notes will be, fully and unconditionally guaranteed, jointly and severally, on the terms and subject to the conditions set forth in the Indenture (the “Outstanding Note Guarantees” and the “Exchange Note Guarantees,” respectively).

All capitalized terms used herein that are defined in, or by reference in, the Indenture have the meanings assigned to such terms therein or by reference therein, unless otherwise defined herein. With your permission, all assumptions and statements of reliance herein have been made without any independent investigation or verification on our part except to the extent otherwise expressly stated, and we express no opinion with respect to the subject matter or accuracy of such assumptions or items relied upon.

In connection with this opinion, we have (i) investigated such questions of law, (ii) examined originals or certified, facsimile, conformed, electronic, photostatic or reproduction copies of such agreements, instruments, documents and records of the Issuers and the Guarantors, such certificates of public officials and such other documents and (iii) received such information from officers and representatives of the Issuers, the Guarantors and others, in each case, as we have deemed necessary or appropriate for the purposes of this opinion. We have examined, among other documents, the following:

(a) The Indenture dated November 2, 2009 between the Issuers, the Guarantors party thereto and Wells Fargo Bank, N.A., as Trustee and Collateral Trustee with respect to the 8 7/8% First Priority Ship Mortgage Notes due 2017 as supplemented from time to time (the “Indenture”);

(b) The Notes; and

(c) The Notations of Guarantee (as defined in the Indenture).

The documents referred to in items (a) through (c) above, inclusive, are collectively referred to as the “Documents.”

In all such examinations, we have assumed the legal capacity of all natural persons, the genuineness of all signatures, the authenticity of original and certified documents and the conformity to original or certified documents of all copies submitted to us as conformed, facsimile, electronic or reproduction copies. As to various questions of fact relevant to the opinions expressed herein, we have relied upon, and assume the accuracy of, representations and warranties contained in the Documents and certificates and oral or written statements and other information of or from public officials, officers or other appropriate representatives of the Issuers, the Guarantors and others, and assume compliance on the part of all parties to the Documents with their respective covenants and agreements contained therein.

To the extent it may be relevant to the opinions expressed herein, we have assumed that (i) the Registration Statement has become effective under the Securities Act and the Indenture has been qualified under the TIA; (ii) the Exchange Notes have been duly authorized and executed by the Issuers and Guarantors (other than the Co-Issuer); (iii) the Exchange Notes have been duly authenticated and delivered by the Trustee; (iv) all of the parties to the Documents (other than the Co-Issuer) are validly existing and in good standing under the laws of their respective jurisdictions of organization and have the power and authority to (a) execute and deliver the Documents, (b) perform their obligations thereunder and (c) consummate the transactions contemplated thereby; (v) each of the Documents has been duly authorized, executed and delivered by all of the parties thereto (other than the Co-Issuer), the execution thereof does not violate the charter, the by-laws or any other organizational document of any such parties or the laws of the jurisdiction of incorporation of any such parties (other than the Co-Issuer), and each of the Documents constitutes valid and binding obligations of all the parties thereto (other than as expressly addressed in the opinions below as to the Issuers and the Guarantors) enforceable against such parties in accordance with their respective terms; and (vi) all of the parties to the Documents will comply with all laws applicable thereto.

Based upon the foregoing, and subject to the limitations, qualifications and assumptions set forth herein, we are of the opinion that:

1. The Exchange Notes, when executed, issued and delivered in accordance with the terms of the Indenture in exchange for the Outstanding Notes, will constitute valid and binding obligations of the Issuers, enforceable against the Issuers in accordance with their terms.

- 2 -

2. The Exchange Note Guarantees by the Guarantors, when the Exchange Notes have been duly executed, issued and delivered in accordance with the terms of the Indenture in exchange for the Outstanding Notes, will constitute a valid and binding obligation of each of the Guarantors, enforceable against each of the Guarantors in accordance with their terms.

The opinions set forth above are subject to the following qualifications:

(A) We express no opinion as to the legality, validity, binding effect or enforceability of any provision of the Documents:

(i) relating to indemnification, contribution or exculpation;

(ii) (a) containing any purported waiver, release, variation, disclaimer, consent or other agreement of similar effect (all of the foregoing, collectively, a “Waiver”) by the Issuers or any Guarantor under any of such Documents, agreements or instruments to the extent limited by provisions of applicable law (including judicial decisions), or to the extent that such a Waiver applies to a right, claim, duty, defense or ground for discharge otherwise existing or occurring as a matter of law (including judicial decisions), except to the extent that such a Waiver is effective under, and is not prohibited by or void or invalid under, provisions of applicable law (including judicial decisions); or (b) with respect to any Waiver in the Guarantees insofar as it relates to causes or circumstances that would operate as a discharge or release of, or defense available to, the Guarantors thereunder as a matter of law (including judicial decisions), except to the extent such Waiver is effective under and is not prohibited by or void or invalid under applicable law (including judicial decisions);

(iii) related to (a) forum selection or submission to jurisdiction (including, without limitation, any waiver of any objection to venue in any court or of any objection that a court is an inconvenient forum) to the extent that the legality, validity, binding effect or enforceability of any such provision is to be determined by any court other than a court of the State of New York, (b) choice of governing law to the extent that the legality, validity, binding effect or enforceability of any such provision is to be determined by any court other than a court of the State of New York or a federal district court sitting in the State of New York in each case applying the law and choice of law principles of the State of New York, (c) service of process except in accordance with applicable law, or (d) waivers of any rights to trial by jury;

(iv) specifying that provisions thereof may be waived only in writing, to the extent that an oral agreement or an implied agreement by trade practice or course of conduct has been created that modifies any provision of such agreement;

(v) purporting to give any person or entity the power to accelerate obligations, foreclose on collateral or require additional collateral at will or without any notice to the Issuers;

(vi) which may be construed to be in the nature of a penalty; and

- 3 -

(vii) with respect to the effect of any law of any jurisdiction other than the State of New York wherein any party to the Documents may be located.

(B) The opinions expressed above are subject to the effect of, and we express no opinions herein as to, the application of state or foreign securities or Blue Sky laws or any rules or regulations thereunder.

(C) We express no opinion as to any agreement, instrument or other document referred to, or incorporated by reference, in any of the Documents, other than the Documents listed in this opinion letter.

(D) Our opinions above are subject to the following:

(i) bankruptcy, insolvency, reorganization, moratorium and other laws (or related judicial doctrines) now or hereafter in effect affecting creditors’ rights and remedies generally;

(ii) general principles of equity (including, without limitation, standards of materiality, good faith, fair dealing and reasonableness, equitable defenses and limits as to the availability of equitable remedies) whether such principles are considered in a proceeding in equity or at law;

(iii) the application of any applicable fraudulent conveyance, fraudulent transfer, fraudulent obligation, or preferential transfer law or any law governing the distribution of assets of any person now or hereafter in effect affecting creditors’ rights and remedies generally; and

(iv) the qualification that certain provisions of the Documents may be unenforceable in whole or in part, but the inclusion of such provisions does not affect the validity of the Documents as a whole, and the Documents and the laws of the State of New York contain adequate provisions for enforcing payment of the obligations governed or secured thereby, subject to the other qualifications in this letter.

(E) We express no opinion as to compliance with the rules and regulations of the FINRA.

(F) Provisions in the Notations of Guarantees and the Indenture that provide that the Guarantors’ liability thereunder shall not be affected by (i) actions or failures to act on the part of the recipient, the holders or the Trustee, (ii) amendments or waivers of provisions of documents governing the guaranteed obligations or (iii) other actions, events or circumstances that make more burdensome or otherwise change the obligations and liabilities of the Guarantors, might not be enforceable under circumstances and in the event of actions that change the essential nature of the terms and conditions of the guaranteed obligations. We have assumed consideration that is fair and sufficient to support the agreements of each Guarantor under the Guarantees and Article Ten of the Indenture has been, and would be deemed by a court of competent jurisdiction to have been, duly received by each Guarantor.

- 4 -

(G) We express no opinion as to the legality, validity, binding effect or enforceability of Section 13.16(a) of the Indenture providing for the Issuers and the Guarantors’ indemnity against loss in connection with obtaining a court judgment in another currency.

(H) We express no opinion as to the legality, validity, binding effect or enforceability of any document that is or may be deemed to be or purports to create a power of attorney.

(I) We express no opinion as to (i) the creation, attachment, validity, binding effect, enforceability or perfection of any security interest, mortgage, pledge, lien or other encumbrance that may be created under any of the Documents, or (ii) the priority or other effect of perfection or non-perfection of any security interest created under any of the Documents.

The opinions expressed herein are limited solely to the federal laws of the United States of America, the laws of the State of New York and, to the extent relevant to the opinions expressed herein, the General Corporation Law of the State of Delaware, each as currently in effect, together with applicable provisions of the Constitution of Delaware and relevant decisional law, and no opinion is expressed with respect to any other laws or any effect that such other laws may have on the opinions expressed herein. Insofar as the opinions expressed herein involve the laws of the Marshall Islands and Liberia, we have relied with your permission on the opinion of Reeder & Simpson P.C. filed as Exhibit 5.2 to the Registration Statement. Insofar as the opinions expressed herein involve the laws of Malta, Belgium and Panama, we have relied with your permission on the opinions of Camilleri, Delia, Randon & Associates, Loyens & Loeff and Vives y Asociados filed as Exhibits 5.3, 5.4 and 5.5, respectively, to the Registration Statement. Furthermore, Loyens & Loeff may rely on our second opinion set forth above, as if it were addressed to them, in rendering their opinion that is filed as Exhibit 5.4 to the Registration Statement.

The opinions expressed herein are limited to the matters stated herein and no opinion is implied or may be inferred beyond the matters expressly stated herein. The opinions expressed herein are given solely as of the date of effectiveness of the Registration Statement, and we undertake no obligation to supplement this letter if any applicable laws change after the date hereof or if we become aware of any facts that might change the opinions expressed herein or for any other reason.

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the reference to this firm under the caption “Legal Matters” in the prospectus that is included in the Registration Statement. In giving this consent, we do not hereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act.

Very truly yours,

/s/ FRIED, FRANK, HARRIS, SHRIVER & JACOBSON LLP

FRIED, FRANK, HARRIS, SHRIVER & JACOBSON LLP

- 5 -

Exhibit A

Faith Marine Ltd.

Vector Shipping Corporation

Aramis Navigation Inc.

Ducale Marine Inc.

Highbird Management Inc.

Red Rose Shipping Corp.

Ginger Services Co.

Quena Shipmanagement Inc.

Astra Maritime Corporation

Primavera Shipping Corporation

Pueblo Holdings Ltd.

Beaufiks Shipping Corporation

Rowboat Marine Inc.

Corsair Shipping Ltd.

Pharos Navigation S.A.

Sizzling Ventures Inc.

Shikhar Ventures S.A.

Taharqa Spirit Corp.

Rheia Associates Co.

Rumer Holding Ltd.

Kleimar N.V.

NAV Holdings Limited

Navios Corporation

Anemos Maritime Holdings Inc.

Navios Shipmanagement Inc.

Aegean Shipping Corporation

Arc Shipping Corporation

Magellan Shipping Corporation

Mandora Shipping Ltd.

Ionian Shipping Corporation

Apollon Shipping Corporation

Herakles Shipping Corporation

Achilles Shipping Corporation

Kypros Shipping Corporation

Hios Shipping Corporation

Meridian Shipping Enterprises Inc.

Mercator Shipping Corporation

Horizon Shipping Enterprises Corporation

Star Maritime Enterprises Corporation

Navios Handybulk Inc.

Navios International Inc.

Nostos Shipmanagement Corp.

Navios Maritime Finance II (US) Inc

- 6 -

Portorosa Marine Corp.

White Narcissus Marine S.A.

Hestia Shipping Ltd.

Kleimar Ltd.

Navimax Corporation

Aquis Marine Corp.

Navios Tankers Management Inc.

Rawlin Services Company

Solange Shipping Ltd.

Serenity Shipping Enterprises Inc

Tulsi Shipmanagement Co.

- 7 -