Exhibit 5.1

ONE SHELL PLAZA 910 LOUISIANA HOUSTON, TEXAS 77002-4995   TEL +1 713.229.1234 FAX +1 713.229.1522 www.bakerbotts.com AUSTIN DALLAS DUBAI HONG KONG HOUSTON LONDON MOSCOW NEW YORK RIYADH WASHINGTON

February 28, 2007

Syntroleum Corporation

4322 South 49th West Avenue

Tulsa, Oklahoma 74107

Ladies and Gentlemen:

As set forth in the Registration Statement on Form S-3 (Registration No. 333-62290) (the “Registration Statement”) filed with the Securities and Exchange Commission (the “Commission”) by Syntroleum Corporation, a Delaware corporation (the “Company”), under the Securities Act of 1933, as amended (the “Securities Act”), relating to (i) the Company’s unsecured senior and subordinated debt securities (the “Debt Securities”); (ii) shares of the Company’s common stock, par value $0.01 per share (the “Common Shares”), and the associated preferred stock purchase rights; (iii) shares of the Company’s preferred stock, par value $0.01 per share (the “Preference Shares”); (iv) depositary shares (the “Depositary Shares”) representing fractional interests in the Preferred Shares; and (v) warrants (the “Warrants”) to purchase Debt Securities, Common Shares, Preferred Shares, Depositary Shares or other securities to be issued and sold by the Company from time to time pursuant to the Securities Act for an aggregate initial offering price not to exceed $250,000,000, certain legal matters in connection with the Common Shares are being passed upon for you by us.

The Registration Statement has been filed with, and declared effective by, the Commission. The Company’s prospectus dated November 20, 2006 and prospectus supplement dated February 28, 2007 (collectively, the “Prospectus”) have been filed with the Commission pursuant to Rule 425(b)(5) under the Securities Act. The Prospectus relates to the proposed issuance and sale by the Company of 1,546,043 Common Shares pursuant to that certain Common Stock Purchase Agreement dated as of November 20, 2006 by and between Azimuth Opportunity Ltd. and the Company (the “Purchase Agreement”).

In our capacity as your counsel in the connection referred to above, we have examined (i) the Registration Statement, (ii) the Company’s certificate of incorporation and bylaws as in effect on the date hereof; (iii) the Purchase Agreement; (iv) the Prospectus and (v) the originals, or copies certified or otherwise identified, of corporate records or other organizational records and documents of the Company, certificates of public officials and of officers or other representatives of the Company, and statutes and other instruments and documents as a basis for the opinions hereafter expressed. We have relied upon the representations and warranties of the Company contained in the Purchase Agreement and certificates of officers of the Company and public officials with respect to the accuracy of the factual matters contained in such certificates. We have assumed that all signatures on documents examined by us are genuine, all documents submitted to us as originals are authentic and complete and all documents submitted to us as certified or photostatic copies are true and correct copies of such documents.

Syntroleum Corporation 2 February 28, 2007

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

1. The Shares have been duly authorized and, when issued and delivered in accordance with the provisions of the Registration Statement and the Prospectus, will be validly issued, fully paid and nonassessable.

We limit the opinions we express above in all respects to matters of the laws of the State of New York, the General Corporation Law of the State of Delaware and the federal securities laws of the United States of America, each as in effect on the date hereof.

We hereby consent to the filing of this opinion of counsel as Exhibit 5.1 to the Current Report on Form 8-K. We also consent to the reference to our Firm under the headings “Legal Opinions” in the Prospectus. 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 or the rules and regulations of the Commission thereunder.

Very truly yours,

/s/ Baker Botts L.L.P.

JDG/JMR