Exhibit 5.1

June 12, 2009

Tsakos Energy Navigation Limited

367 Syngrou Avenue

175 64 P. FALIRO

ATHENS, GREECE

Re: Tsakos Energy Navigation Limited’s Registration Statement on Form F-3

Ladies and Gentlemen:

We have acted as special Bermuda counsel to Tsakos Energy Navigation Limited, a Bermuda company (the “Company”), in connection with the filing of a Registration Statement on Form F-3, as amended, including the exhibits thereto (the “Registration Statement”), under the Securities Act of 1933, as amended (the “Act”) and the rules and regulations promulgated thereunder. The Registration Statement relates to the offer and sale by the Company pursuant to Rule 415 under the Act from time to time of an indeterminate amount of securities which may include (i) its Common Shares, Preferred Shares, Warrants, Debt Securities, Depositary Shares, Purchase Contracts and Units, and (ii) its Common Shares that may be sold by or on behalf of certain selling shareholders of the Company or their donees, pledgees, transferees or other successors in interest (the “Resale Shares”, and together with the Common Shares, Preferred Shares, Warrants, Debt Securities, Depositary Shares, Purchase Contracts and Units, the “Securities”). Except as otherwise defined herein, capitalized terms are used as defined in the Registration Statement.

In connection with this opinion, we have examined originals, or copies certified or otherwise identified to our satisfaction, of the Company’s Certificate of Incorporation, Certificates of Incorporation on Change of Name, Certificate of Registration of Altered Memorandum of Association, Memorandum of Association and Bye-laws (collectively, the “Constitutional Documents”), a Certificate of Compliance dated June 12, 2009 (the “Certificate of Compliance”) issued by the Registrar of Companies in Bermuda (the “Registrar”), the Registration Statement and the form of prospectus included therein, the form of indenture to be entered into by the Company and Wells Fargo Bank, National Association (formerly Wells Fargo Bank Minnesota, National Association), as trustee (incorporated by reference as Exhibit 4.1 to the Registration Statement) (the “Senior Indenture”), the form of subordinated indenture to be entered into by the Company and Wells Fargo Bank, National Association (formerly Wells Fargo Bank Minnesota, National Association), as trustee (incorporated by reference as Exhibit 4.2 to the Registration Statement) (the “Subordinated Indenture” and collectively with the Senior Indenture referred to herein as the “Subject Agreements”), the resolutions of the Board of Directors of the Company dated May 12, 2009 (the “Resolutions”) and such other documents and records as we have deemed necessary. The documents referred to in this paragraph are collectively referred to herein as the “Documents”.

1

In our examination of the Documents, we have assumed, without independent investigation, the genuineness of all signatures, the legal capacity of all individuals who have executed any of the Documents, the authenticity of all Documents submitted to us as originals, the conformity to the original documents of all Documents submitted to us as certified, photostatic, reproduced or conformed copies and the authenticity of all such Documents. For the purposes of this opinion, we have relied solely upon a Certificate of the Secretary of the Company dated the date hereof as to the due adoption and continued effectiveness as of the date hereof of all the Resolutions.

We have also assumed that (i) the form of the Subject Agreements and Registration Statement which we have examined for the purposes of this opinion do not differ in any material respect from those approved by the Board of Directors of the Company pursuant to the Resolutions, and that, when filed (in respect of the Registration Statement) or executed and delivered (in respect of the Subject Agreements), the Registration Statement and the Subject Agreements will be in a form which does not differ in any material respect from the forms we have examined for the purposes of this opinion, (ii) the definitive terms of the Securities, other than Common Shares, offered pursuant to the Registration Statement will have been established in accordance with the Resolutions and applicable law, (iii) any Securities issuable upon conversion, exchange or exercise of any Security being offered, will be duly authorized, created and, if appropriate, reserved for issuance upon such conversion, exchange or exercise, (iv) any Securities consisting of Common Shares or Preferred Shares, including Common Shares or Preferred Shares issuable upon conversion, exchange or exercise of any Security being offered, will be duly authorized and issued, and the certificates evidencing the same will be duly executed and delivered, against receipt of the consideration approved by the Company which will be no less than the par value, if any, thereof, (v) the Registration Statement, and any amendments thereto, will have become effective, (vi) a Prospectus Supplement will have been filed with the Securities and Exchange Commission (the “Commission”) describing the Securities offered thereby, (vii) all Securities will be issued in compliance with applicable U.S. federal and state securities and other laws (other than the laws of Bermuda in respect of which we are opining), and (viii) prior to the date of issuance of any Securities, all necessary approvals of the Bermuda Monetary Authority (save in the case of the issuance of the Common Shares) will have been obtained with respect to the issue and free transferability of the Securities to be issued.

For the purpose of the opinions set forth below, we have also assumed:

• with respect to the issuance and sale of any Debt Securities, that (i) with respect to any Senior Debt Securities, the Senior Indenture will have been duly executed and delivered by the Company and the trustee named therein, (ii) with respect to any Subordinated Debt Securities, the Subordinated Indenture will have been duly executed and delivered by the Company and the trustee named therein, and (iii) with respect to all Debt Securities, when issued, will be executed, authenticated, issued and delivered (a) against receipt of the consideration therefor approved by the Company and (b) as provided in the indenture with respect thereto;

• with respect to the issuance and sale of any series of Preferred Shares or any Depositary Shares, that an appropriate certificate of designations, or similar instrument setting forth

2

the preferential, qualified or special rights, privileges or conditions with respect to such series of Preferred Shares will have been duly and validly authorized and adopted by the Company;

• with respect to the issuance and sale of any Warrants, that (i) a warrant agreement with respect to such Warrants will have been executed and delivered by the Company and the warrant agent, (ii) the warrant agreement will be governed by Bermuda law, (iii) the Warrants will have been duly and validly authorized, created, executed and delivered by the Company and duly executed by any warrant agent appointed by the Company, and (iv) the Warrants will have been issued and delivered by the Company against receipt of the consideration therefor approved by the Company;

• with respect to the issuance and sale of Depositary Shares, that (i) a deposit agreement with respect to such Depositary Shares will have been executed and delivered by the parties thereto, (ii) the deposit agreement will be governed by Bermuda law, (iii) the Depositary Shares will have been duly and validly authorized, created, executed and delivered by the Company and duly executed by any depositary appointed by the Company, and (iv) the Depositary Shares will have been issued and delivered by the Company against receipt of the consideration therefor approved by the Company;

• with respect to the issuance and sale of any Purchase Contracts, that (i) a purchase agreement with respect to such Purchase Contracts will have been executed and delivered by the parties thereto, (ii) the purchase agreement will be governed by Bermuda law, and (iii) the Purchase Contracts will have been duly executed and delivered in accordance with the purchase agreement upon payment of the consideration therefor provided for therein; and

• with respect to the issuance and sale of any Units, that (i) a purchase agreement with respect to such Units will have been executed and delivered by the parties thereto, (ii) the purchase agreement with respect to the Units will be governed by Bermuda law, and (iii) the Units, if in certificated form, will have been duly executed and delivered in accordance with the purchase agreement upon payment of the consideration therefor provided for therein.

Based upon and subject to the foregoing and subject to the reservations set out below and to any matters not disclosed to us, we are of the opinion that:

1. The Company has been duly incorporated and is validly existing and in good standing as an exempted company under the laws of Bermuda. We have relied solely on the Certificate of Compliance for our opinion that the Company is in “good standing”.

2. The Resale Shares are validly issued, fully paid and non-assessable.

3. Any Securities consisting of Common Shares or Preferred Shares, including any Common Shares or Preferred Shares issuable on conversion, exercise or exchange of other Securities, when issued and delivered, will be duly and validly issued, fully paid and non-assessable.

4. Any Securities consisting of Debt Securities, Warrants, Depositary Shares, Purchase Contracts or Units will constitute legal, valid and binding obligations of the Company and will be, in the case of Debt Securities, entitled to the benefits provided by the applicable indenture.

3

We have the following reservations (i) we express no opinion as to any law other than Bermuda law and none of the opinions expressed herein relates to compliance with or matters governed by the laws of any jurisdiction except Bermuda, and (ii) any reference in this opinion to shares being “non-assessable” shall mean, in relation to fully-paid shares of the Company and subject to any contrary provision in any agreement in writing between the Company and a holder of shares (but only with respect to such holder), that no shareholder shall be obliged to contribute further amounts to the capital of the Company, either in order to complete payment for their shares, to satisfy claims of creditors of the Company, or otherwise; and no shareholder shall be bound by an alteration of the Memorandum of Association or Bye-laws of the Company after the date on which he became a shareholder, if and so far as the alteration requires him to take, or subscribe for additional shares, or in any way increase his liability to contribute to the share capital of, or otherwise to pay money to, the Company.

This opinion is issued solely for the purpose of the filing of the Registration Statement and for no other purpose. Except for such use, this opinion may not be quoted, circulated or published, in whole or in part, or otherwise referred to without our express prior written authorization. We consent to the filing of this opinion as Exhibit 5.1 to the Registration Statement and to the use of our name under the caption “Legal Matters”. In giving this consent, we do not admit that we are acting within the category of persons whose consent is required under Section 7 of the Act. Further, this opinion speaks as of its date and is strictly limited to the matters stated herein and we assume no obligation to review or update this opinion if applicable laws or the existing facts or circumstances should change.

This opinion is to be governed by and construed in accordance with the laws of Bermuda.

Yours faithfully,

/s/ MELLO JONES & MARTIN

4