Exhibit 8.1

July 25, 2012

Crestwood Midstream Partners LP

700 Louisiana Street, Suite 2060

Houston, Texas 77002

Ladies and Gentlemen:

We have acted as counsel to Crestwood Midstream Partners LP, a Delaware limited partnership (the “Partnership”), with respect to certain legal matters in connection with the offer and sale by the Partnership of its common units representing limited partner interests (the “Common Units”). We have also participated in the preparation of the Partnership’s prospectus dated April 28, 2011 (the “Prospectus”) and the Partnership’s prospectus supplement dated July 25, 2012 (the “Prospectus Supplement”) forming part of the Partnership’s Registration Statement on Form S-3, as amended (File No. 333-171735) (the “Registration Statement”).

In connection therewith, we prepared the discussion (the “Discussion”) set forth under the caption “Material Tax Considerations” in the Prospectus and the Prospectus Supplement, respectively.

We hereby confirm that all statements of legal conclusions contained in the Discussion reflect the opinion of Locke Lord LLP with respect to the matters set forth therein (i) as of the date of the Prospectus in respect of the discussion set forth under the caption “Material Tax Considerations” in the Prospectus, and (ii) as of the date of the Prospectus Supplement in respect of the discussion set forth under the caption “Material Tax Considerations” in the Prospectus Supplement, subject to the assumptions, qualifications, exceptions and limitations set forth therein, and excepting the representations and statements of fact of the Partnership and its general partner included in the Discussion, as to which we express no opinion.

In providing this opinion, we have examined and are relying upon the truth and accuracy at all relevant times of the statements, covenants, and representations contained in (i) the Registration Statement, Prospectus and Prospectus Supplement, (ii) certain other filings made by the Partnership with the Securities and Exchange Commission (“SEC”) and (iii) other information provided to us by the Partnership and its general partner.

This opinion is furnished to you, and is for your use in connection with the transactions set forth in the Registration Statement. This opinion may not be relied upon by you for any other purpose or furnished to, assigned to, quoted to or relied upon by any other person, firm or other entity, for any purpose, without our prior written consent. However, this opinion may be relied upon by you and by persons entitled to rely on it pursuant to applicable provisions of federal securities law, including persons purchasing limited partnership units or other classes of units pursuant to the Registration Statement.

July 25, 2012

Page 2

We hereby consent to the filing of this opinion as an exhibit to the Current Report on Form 8-K and to the use of our name in the Discussion in the Prospectus and Prospectus Supplement. In giving this consent, we do not hereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the SEC thereunder.

Very truly yours,

/s/ Locke Lord LLP

LOCKE LORD LLP