Exhibit 5.1

21 September 2012

Tsakos Energy Navigation Limited

367 Syngrou Avenue

175 64 P. Faliro

Athens, Greece

Dear Sirs,

Tsakos Energy Navigation Limited (the “Company”)

1. Subject of Opinion

We have acted as special legal counsel in Bermuda to the Company in connection with a registration statement on Form F-3 to be filed with the United States Securities and Exchange Commission (the “Commission”) on 21 September 2012 (the “Registration Statement”, which term does not include any other document or agreement whether or not specifically referred to therein or attached as an exhibit or schedule thereto) relating to the offer and sale by the Company pursuant to Rule 415 under the United States Securities Act of 1933, as amended (the “Securities Act”) from time to time of securities which may include (i) its Common Shares, Preferred Shares, Warrants, rights other than Preferred Share Purchase Rights (the “Rights”), 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, preferred share purchase rights relating to each Common Share (the “Preferred Share Purchase Rights”), Rights, Debt Securities, Depositary Shares, Purchase Contracts and Units, the “Securities”). This opinion also relates to any registration statement on Form F-3 in connection with this offering that is to be effective upon filing pursuant to Rule 462(b) under the Securities Act. Except as otherwise defined herein, capitalized terms are used as defined in the Registration Statement.

Tsakos Energy Navigation Limited (the “Company”) 21 September 2012 Page 2

2. Documents Examined

For the purposes of giving this opinion, we have examined a copy of the Registration Statement and the form of prospectus included therein, the rights agreement dated as of September 29, 2005, between the Company and The Bank of New York, as Rights Agent (the “Rights Agreement”, the form of indenture to be entered into by the Company and Wells Fargo Bank, National Association, as trustee (the “Senior Indenture”), the form of subordinated indenture to be entered into by the Company and Wells Fargo Bank, National Association, as trustee (the “Subordinated Indenture”), the form of convertible indenture to be entered into by the Company and Wells Fargo Bank, National Association, as trustee (the “Convertible Indenture” and, together with the Rights Agreement, the Senior Indenture and the Subordinated Indenture, referred to herein as the “Subject Agreements”, which term does not include any other document or agreement whether or not specifically referred to therein or attached as an exhibit or schedule thereto). We have also reviewed copies of the memorandum of association and the bye-laws of the Company (together, the “Constitutional Documents”), each certified by the Resident Representative of the Company on 20 September 2012, minutes of a meeting of the board of directors held on September 28, 2005 (the “Authorizing Resolution”), a copy of a register of major shareholders of the Company dated 20 August 2012, certified by the Resident Representative of the Company on 21 September 2012 and such other documents and made such enquiries as to questions of law as we have deemed necessary in order to render the opinion set forth below.

3. Assumptions

We have assumed (a) the genuineness and authenticity of all signatures and the conformity to the originals of all copies (whether or not certified) of all documents examined by us and the authenticity and completeness of the originals from which such copies were taken, (b) that where a document has been examined by us in draft form, it will be or has been executed and/or filed in the form of that draft, and where a number of drafts of a document have been examined by us all changes thereto have been marked or otherwise drawn to our attention, (c) the accuracy and completeness of all factual representations made in the Registration Statement, the Subject Agreements and other documents reviewed by us, (d) that the resolutions contained in the Authorizing Resolution were passed at one or more duly convened, constituted and quorate meetings, or by unanimous written resolutions, remain in full force and effect and have not been rescinded or amended, (e) that the Authorizing Resolution contains all resolutions affecting the Rights Agreement, (f) the due execution and delivery of the Rights Agreement by each of the parties thereto, other than the Company, (g) that on the date of entering into the Rights Agreement the Company was and after entering into the Rights Agreement the Company will be able to pay its liabilities as they become due, (h) that the board of directors of the Company has exercised the power to adopt the Rights Agreement for a proper purpose, (i) that the Constitutional Documents will not be amended in any manner that would affect the opinions expressed herein, (j) that there is no provision of the law of any jurisdiction, other than Bermuda, which would have any implication in relation to the opinions expressed herein, (k) that the Resale Shares were in issuance on 20 August 2012, (l) that the Common Shares will be listed on an appointed stock exchange, as defined in the Companies Act 1981, as amended (the “Companies Act”), and the consent to the issue and free transfer of the Securities given by the Bermuda Monetary Authority pursuant to its Notice to the Public dated 1 June 2005 will not

Tsakos Energy Navigation Limited (the “Company”) 21 September 2012 Page 3

have been revoked or amended at the time of issuance of any Securities, (m) that the Company will have sufficient authorised share capital to effect the issue of any of the Securities consisting of Common Shares, Preferred Shares or Depositary Shares at the time of issuance as a principal issue or upon the conversion, exchange or exercise of any Security being offered, (n) that the form and terms of any and all Securities (including, without limitation, the designation, powers, preferences, rights, qualifications, limitations, privileges, conditions and restrictions of Preferred Shares) or other securities comprising the same or subject thereto (in the case of the Warrants and Units), the issuance and sale thereof by the Company, and the Company’s incurrence and performance of its obligations thereunder or in respect thereof (including, without limitation, its obligations under any related agreement, indenture or supplement thereto) in accordance with the terms thereof will not violate the Constitutional Documents nor any applicable law, regulation, order or decree in Bermuda, (o) that all necessary corporate action will be taken to authorise and approve the creation and any issuance of Securities (including, if Preferred Shares or Depositary Shares are to be issued, all necessary corporate action to establish one or more series of Preferred Shares and fix the designation, powers, preferences, rights, qualifications, limitations, privileges, conditions and restrictions thereof), the terms of the offering thereof and related matters, and that the applicable warrant, rights, deposit, purchase, underwriting or similar agreement, the Senior Indenture, the Subordinated Indenture, the Convertible Indenture and any applicable supplements thereto will be duly approved, executed and delivered by or on behalf of the Company and all other parties thereto, (p) that the applicable warrant, rights, deposit, purchase, underwriting or similar agreement, the Senior Indenture, the Subordinated Indenture, the Convertible Indenture and any applicable supplements thereto and any other agreement or other document relating to any Security will be valid and binding in accordance with its terms pursuant to its governing law, (q) that the issuance and sale of and payment for the Securities will be in accordance with the applicable warrant, rights, deposit, purchase, underwriting or similar agreement, the Senior Indenture, the Subordinated Indenture, the Convertible Indenture and any applicable supplements thereto, duly approved by the Board of Directors and the Registration Statement (including the prospectus set forth therein and any applicable supplement thereto), (r) that, upon the issue of any of the Securities consisting of Common Shares, Preferred Shares or Depositary Shares, the Company will receive consideration for the full issue price thereof which shall be equal to at least the par value thereof, (s) that the Company will comply, to the extent applicable, with the requirements of Part III of the Companies Act entitled “Prospectuses and Public Offers”, (t) the capacity, power and authority of all parties other than the Company to enter into and perform their obligations under any and all documents entered into by such parties in connection with the issuance of the Securities and the due execution and delivery thereof by each party thereto, and (u) none of the parties to such documents carries on business from premises in Bermuda, at which it employs staff and pays salaries and other expenses.

4. Opinion Limited to Bermuda Law

We have made no investigation of and express no opinion in relation to the laws of any jurisdiction other than Bermuda. This opinion is to be governed by and construed in accordance with the laws of Bermuda and is limited to and is given on the basis of the current law and practice in Bermuda. This opinion is issued solely for the purposes of the filing of the Registration Statement and the issuance of the Securities by the Company and is not to be relied upon in respect of any other matter.

Tsakos Energy Navigation Limited (the “Company”) 21 September 2012 Page 4

5. Opinion

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:

5.1. The Company has been duly incorporated and is validly existing under the laws of Bermuda.

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

5.3. The issuance of the Preferred Share Purchase Rights was duly authorized by the Board of Directors on September 28, 2005 pursuant to the Authorizing Resolution.

5.4. The Rights Agreement was duly authorized by the Board of Directors on September 28, 2005 pursuant to the Authorizing Resolution.

5.5. The Preferred Share Purchase Rights relating to the Resale Shares are legal and valid and the holders thereof have no personal liability as such under the existing laws of Bermuda, which is the jurisdiction in which the Company is organized.

5.6. Upon the issuance of the Preferred Share Purchase Rights relating to Common Shares other than the Resale Shares in accordance with the Rights Agreement, the Preferred Share Purchase Rights will be legal and valid and the holders of such Preferred Share Purchase Rights will have no personal liability as such under the existing laws of Bermuda, which is the jurisdiction in which the Company is organized.

5.7. 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.

5.8. Any Securities consisting of Debt Securities, Warrants, Rights, Depositary Shares, Purchase Contracts or Units will constitute the legal, valid and binding obligations of the Company in accordance with the terms thereof.

Tsakos Energy Navigation Limited (the “Company”) 21 September 2012 Page 5

6. Reservations

Our reservations are as follows:

6.1. The enforceability of the obligations of the Company in connection with any Security, any of the Subject Agreements and any other agreement or other document relating to any Security may be subject to limitations and restrictions under applicable bankruptcy, insolvency, liquidation, reorganisation or similar laws affecting creditors’ rights generally;

6.2. Claims may become barred under the Limitation Act 1984, as amended, or other legislation relating to legal limitation periods or may be or become subject to defences of set-off or counter-claim;

6.3. Where any obligations are to be performed or observed in a jurisdiction outside Bermuda, they may not be enforceable under Bermuda law if and to the extent that such performance or observance would be unlawful, unenforceable or contrary to public policy under the laws of such jurisdiction;

6.4. Equitable remedies such as specific performance and injunctive relief are only available at the discretion of a Bermuda court; moreoever, the exercise of legal rights may be affected by equitable considerations and a Bermuda court also has power to stay any proceedings either of its own motion or on the application of any person;

6.5. A Bermuda court might not enforce in full the provisions of any Security, any of the Subject Agreements and any other agreement or other document relating to any Security which requires the Company to pay any additional amount (including interest) on any overdue sum, on the grounds that such provisions may not constitute a genuine pre-estimate of the loss suffered in the circumstances therein envisaged.

We express no opinion as to the enforceability of any specific provision of the Rights Agreement.

7. Consent

We hereby consent to the filing of this opinion as Exhibit 5.1 to the Registration Statement and to the reference to our firm under the caption “Legal Matters”. In giving such consent, we do not hereby admit that we are experts within the meaning of Section 11 of the Securities Act or that we are in the category of persons whose consent is required under Section 7 of the Securities Act or the Rules and Regulations of the Commission promulgated thereunder.

Yours faithfully,

MJM Limited