Exhibit 5.1

Opinion of Sullivan & Cromwell LLP

February 27, 2009

First Midwest Bancorp, Inc.,

One Pierce Place, Suite 1500,

Itasca, Illinois 60143.

Ladies and Gentlemen:

In connection with the registration under the Securities Act of 1933 (the “Act”) of an unspecified aggregate amount or number of (i) shares of common stock, par value $0.01 per share (the “Common Stock”), and the related stock purchase rights (the “Rights”) to purchase Participating Preferred Stock to be issued pursuant to the Amended and Restated Rights Agreement, dated November 15, 1995, between First Midwest Bancorp, Inc. and First Midwest Bank, as Rights Agent (the “Rights Agent”), as amended by the First Amendment to the Amended and Restated Rights Agreement, dated June 18, 1997, the Second Amendment to the Amended and Restated Rights Agreement, dated November 14, 2005 and the Third Amendment to the Amended and Restated Rights Agreement, dated December 3, 2008 (as so amended, the “Rights Agreement”), (ii) shares of preferred stock, without par value (the “Preferred Stock”), (iii) depositary shares (evidenced by depositary receipts) representing interests in shares of Preferred Stock, (iv) debt securities, (v) warrants, (vi) stock purchase contracts and stock purchase units and (vii) units composed of the foregoing (collectively, the “Securities”) of First Midwest Bancorp, Inc., a Delaware corporation (the “Company”), we, as your counsel, have examined such corporate records, certificates and other documents, and such questions of law, as we have considered necessary or appropriate for the purposes of this opinion.

Upon the basis of such examination, we advise you that, in our opinion:

(1) When the registration statement on Form S-3 relating to the Securities (the “Registration Statement”) has become effective under the Act, the terms of the sale of the Common Stock have been duly established in conformity with the Company’s certificate of incorporation so as not to violate any applicable law or result in a default under or breach of any agreement or instrument binding on the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, and the Common Stock has been duly issued and sold as contemplated in the Registration Statement, the Common Stock will be validly issued, fully paid and nonassessable.

First Midwest Bancorp, Inc. - 2 -

(2) Assuming that the Rights Agreement has been duly authorized, executed and delivered by the Rights Agent, then when the Registration Statement has become effective under the Act and the Common Stock has been validly issued and sold as contemplated in the Registration Statement, the Rights attributable to the Common Stock will be validly issued.

(3) When the Registration Statement has become effective under the Act, a certificate of designations with respect to the Preferred Stock has been duly filed with the Secretary of State of the State of Delaware, the terms of the Preferred Stock and of its issuance and sale have been duly established in conformity with the Company’s certificate of incorporation so as not to violate any applicable law or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, and the Preferred Stock has been duly issued and sold as contemplated in the Registration Statement, the Preferred Stock will be validly issued, fully paid and nonassessable.

(4) When the Registration Statement has become effective under the Act, the terms of the deposit agreement under which the depositary shares are to be issued (the “Deposit Agreement”) have been duly established so as not to violate any applicable law or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, the Deposit Agreement has been duly authorized, executed and delivered, the terms of the depositary shares and of their issuance and sale have been duly established in conformity with the Deposit Agreement so as not to violate any applicable law or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, the Preferred Stock represented by the depositary shares has been duly authorized and validly issued and delivered to the depositary, and the depositary receipts evidencing the depositary shares have been duly issued against deposit of the Preferred Stock in accordance with the Deposit Agreement and issued and sold as contemplated in the Registration Statement, the depositary receipts evidencing the depositary shares will entitle the holders thereof to the rights specified in the Deposit Agreement, subject to bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium and similar laws of general applicability relating to or affecting creditors’ rights and to general equity principles.

First Midwest Bancorp, Inc. - 3 -

(5) When the Registration Statement has become effective under the Act, the indenture (the “Indenture”) relating to a debt security of the Company (a “Debt Security”) has been duly authorized, executed and delivered, the terms of such Debt Security and of its issuance and sale have been duly established in conformity with the Indenture so as not to violate any applicable law or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, and such Debt Security has been duly executed and authenticated in accordance with such Indenture and issued and sold as contemplated in the Registration Statement, such Debt Security will constitute a valid and legally binding obligation of the Company, subject to bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium and similar laws of general applicability relating to or affecting creditors’ rights and to general equity principles.

(6) When the Registration Statement has become effective under the Act, the terms of the warrant agreement under which a particular warrant of the Company (a “Warrant”) is to be issued (the “Warrant Agreement”) have been duly established so as not to violate any applicable law or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, the Warrant Agreement has been duly authorized, executed and delivered, the terms of such Warrant and of its issuance and sale have been duly established in conformity with the Warrant Agreement so as not to violate any applicable law or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, and such Warrant has been duly executed and authenticated in accordance with the Warrant Agreement and issued and sold as contemplated in the Registration Statement, such Warrant will constitute a valid and legally binding obligation of the Company, subject to bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium and similar laws of general applicability relating to or affecting creditors’ rights and to general equity principles.

(7) When the Registration Statement has become effective under the Act, the terms of the governing instrument or agreement under which a particular stock purchase contract or stock purchase unit of the Company (the “Stock Purchase Security”) is to be issued (the “Stock Purchase Agreement”) have been duly established so as not to violate any applicable law or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, the Stock Purchase Agreement has been duly authorized, executed and delivered, the terms of such Stock Purchase Security and of its issuance and sale have been duly established in conformity with the Stock Purchase Agreement so as not to violate any applicable law or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court

First Midwest Bancorp, Inc. - 4 -

or governmental body having jurisdiction over the Company, and such Stock Purchase Security has been duly executed and authenticated in accordance with the Stock Purchase Agreement and issued and sold as contemplated in the Registration Statement, such Stock Purchase Security will constitute a valid and legally binding obligation of the Company, subject to bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium and similar laws of general applicability relating to or affecting creditors’ rights and to general equity principles.

(8) When the Registration Statement has become effective under the Act, the terms of the governing instrument or agreement under which a particular unit of the Company (a “Unit”) is to be issued (the “Unit Agreement”) have been duly established so as not to violate any applicable law or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, the Unit Agreement has been duly authorized, executed and delivered, the terms of such Unit and of its issuance and sale have been duly established in conformity with the Unit Agreement so as not to violate any applicable law or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, and such Unit has been duly executed and authenticated in accordance with the Unit Agreement and issued and sold as contemplated in the Registration Statement, such Unit will constitute a valid and legally binding obligation of the Company, subject to bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium and similar laws of general applicability relating to or affecting creditors’ rights and to general equity principles.

In connection with our opinion set forth in paragraph (2) above, we note that the question whether the Board of Directors of the Company might be required to redeem the Rights at some future time will depend on the facts and circumstances existing at that time and, accordingly, is beyond the scope of such opinion.

We note that, as of the date of this opinion, a judgment for money in an action based on a Debt Security, Warrant, Stock Purchase Security or Unit denominated in a foreign currency or currency unit (collectively, the “Foreign Currency Securities”) in a Federal or state court in the United States ordinarily would be enforced in the United States only in United States dollars. The date used to determine the rate of conversion of the foreign currency or currency unit in which a particular Foreign Currency Security is denominated into United States dollars will depend on various factors, including which court renders the judgment. In the case of a Foreign Currency Security denominated in a foreign currency, a state court in the State of New York rendering a judgment on such Foreign Currency Security would be required under Section 27 of the New York Judiciary Law to render such judgment in the foreign currency in which the Foreign Currency Security is denominated, and such judgment would be converted into United States dollars at the exchange rate prevailing on the date of entry of the judgment.

First Midwest Bancorp, Inc. - 5 -

The foregoing opinion is limited to the Federal laws of the United States, the laws of the State of New York and the General Corporation Law of the State of Delaware, and we are expressing no opinion as to the effect of the laws of any other jurisdiction. In rendering the foregoing opinions, we have assumed, without independent verification, that the Company has been duly incorporated and is an existing corporation in good standing under the laws of the State of Delaware.

We have relied as to certain factual matters on information obtained from public officials, officers of the Company and other sources believed by us to be responsible.

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the references to us under the heading “Validity of the Securities” in the prospectus contained in the Registration Statement. In giving such consent, we do not thereby admit that we are in the category of persons whose consent is required under Section 7 of the Act.

Very truly yours,

/s/ Sullivan & Cromwell LLP