Exhibit 23.1

CONSENT OF INDEPENDENT REGISTERED PUBLIC ACCOUNTING FIRM

We consent to the incorporation by reference in Registration Statement No. 333-171735 on Form S-3 and Registration Statement Nos. 333-145326 and 333-162928 on Forms S-8 of our report dated March 18, 2013 (which report expresses an unqualified opinion and includes an explanatory paragraph concerning the retroactive effect of the common control acquisition of Crestwood Marcellus Midstream LLC), relating to the supplemental consolidated financial statements of Crestwood Midstream Partners LP and subsidiaries, appearing in this Current Report on Form 8-K of Crestwood Midstream Partners LP.

/s/ DELOITTE & TOUCHE LLP

Houston, Texas

March 18, 2013