EXHIBIT 5.4

November 10, 2003

Tsakos Energy Navigation Limited

367 Syngrou Avenue

175 64 P. Faliro

Athens, Greece

Dear Sirs,

re: Registration Statement on Form F-3

We act as special legal counsel in Malta to Tsakos Energy Navigation Limited (the “Company”), a Bermuda Company, in connection with the Company’s debt securities which have been registered under the Securities Act of 1933, as amended (the “Securities Act”) pursuant to a Registration Statement on Form F-3 (the “Registration Statement”).

For the purposes of this opinion we have examined the form of Guarantee included in the Indentures filed as exhibits to the Registration Statement, the relevant documents of Horizana Shipping Company Ltd. and Fortitude Shipping Company Ltd (the “Maltese Guarantors”), the corporate authorizations relevant to the above transaction and other such documents and certificates that we have deemed necessary for the purposes of the opinions expressed below. In such examination we have assumed the genuineness of all signatures and the authenticity of all documents including photocopies and facsimile copies of documents submitted to us as drafts or originals and the conformity with the original of all documents submitted to us as copies.

We express no opinion as to the laws of any jurisdiction other than Malta.

Based on the foregoing and subject to the qualifications and assumptions expressed herein, we are of the opinion that:

The Subsidiary Guarantees (as defined in the Indentures and filed as exhibits to the Registration Statement) have been duly authorized, executed and delivered by the Maltese Guarantors and constitute valid and legally binding obligations of the Maltese Guarantors, enforceable against the Maltese Guarantors in accordance with their terms, except as (A) such enforceability may be limited by bankruptcy, insolvency, fraudulent transfer, fraudulent conveyance, reorganization, arrangement, moratorium or similar laws relating to or affecting the enforcement of creditors’ rights generally and may be subject to general principles of equity (regardless of whether such enforceability is considered in a proceeding in equity or at law,) (B) the availability of equitable remedies may be limited by equitable principles of general applicability.

In rendering such opinion we may rely as to matters of fact, to the extent we deem proper, on certificates of responsible officers of the Company, the Maltese Guarantors and public officials.

We consent to the reference to our firm under heading “Legal Matters” contained in the prospectus filed as part of the Registration Statement and we consent to the filing of this opinion as an exhibit to the Registration Statement. In giving this consent, we do not thereby admit that we are within the category of person whose consent is required to be filed with the Registration Statement under the provisions of the Securities Act or the rules and regulations promulgated thereunder.

Very truly yours,

/s/    FENECH & FENECH

Fenech & Fenech

Advocates

2