Exhibit 5.1

February 19, 2013

Board of Directors

Cytomedix, Inc.

209 Perry Parkway, Suite 7

Gaithersburg, MD 20877

Gentlemen:

You have requested our opinion with respect to certain matters in connection with the offering by Cytomedix, Inc., a Delaware corporation (the “Company”), of (i) an aggregate of 9,090,910 shares of the Company’s common stock, par value $0.0001 (the “Common Stock”) (the “Shares”), warrants to purchase 6,363,637 shares of Common Stock (the “Warrants”) and 6,363,637 shares of Common Stock underlying such warrants (the “Warrant Shares”), pursuant to securities purchase agreements dated as of February 19, 2013 (the “Purchase Agreements”) and (ii) warrants to purchase 136,364 shares of Common Stock issued to Burrill Securities LLC, the Company’s placement agent in connection with the offering of the Shares and Warrants pursuant to the Placement Agency Agreement dated as of February 19, 2013 (the “PA Agreement”) (the “Placement Agent Warrants”) and 136,364 shares of Common Stock underlying such warrants (the “Placement Agent Warrant Shares”) (the Shares, the Warrants and the Warrant Shares, the Placement Agent Warrants and the Placement Agent Warrant Shares, collectively, the “Securities”), pursuant to the Registration Statement on Form S-3 (Registration Statement No. 333-183704) (the “Registration Statement”), filed with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Act”), the prospectus included within the Registration Statement (the “Base Prospectus”), and the supplemented form of prospectus relating to the Securities dated February 19, 2013 and filed with the Commission pursuant to Rule 424(b) of the Rules and Regulations of the Act (the “Prospectus Supplement”). (The Base Prospectus and Prospectus Supplement are collectively referred to as the “Prospectus.”) All of the Securities to be sold by the Company as described in the Registration Statement and Prospectus.

In connection with this opinion letter, we have examined the Registration Statement, the Prospectus, the Purchase Agreements, the PA Agreement, the forms of Warrants and the Placement Agent Warrants, originals, or copies certified or otherwise identified to our satisfaction, of the Company’s certificate of incorporation and bylaws, and any amendments thereto, and such other documents, records and other instruments as we have deemed appropriate for purposes of the opinion set forth herein. In our examination, we have assumed (a) the authenticity of original documents and the genuineness of all signatures, (b) the conformity to the originals of all documents submitted to us as copies or telecopies, and (c) the truth, accuracy and completeness of the information, representations and warranties contained in the records, documents, instruments and certificates we have reviewed. With regard to the Warrant Shares and the Placement Agent Warrants, we have assumed that at the time of issuance or sale, a sufficient number of shares of the Common Stock are authorized and available for issuance.

On the basis of the foregoing and in reliance thereon, we are of the opinion that:

(i)          the Shares, when issued and sold in accordance with and in the manner described in the Registration Statement and the Prospectus, will be duly authorized, validly issued, fully paid and non-assessable,

(ii)          the Warrants and the Placement Agent Warrants have been duly authorized by the Board of Directors of the Company, and constitute valid and binding obligations of the Company enforceable against the Company in accordance with their terms, and

(iii)          the Warrant Shares and the Placement Agent Warrant Shares, when issued and sold in accordance with the terms of the Warrants and the Placement Agent Warrants, respectively, will be duly authorized, validly issued, fully paid and non-assessable.

This opinion is limited to the Federal law of the United States, and the applicable statutory provisions of General Corporation Law of the State of Delaware, including all applicable provisions of the Delaware Constitution. The Securities may be issued from time to time on a delayed or continuous basis, and our opinion is limited to the laws as in effect on the date hereof.

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the reference made to this firm in the Registration Statement under the heading “Legal Matters.”

In giving such consent, we do not believe that we are “experts” within the meaning of such term used in the Securities Act or the rules and regulations of the Securities and Exchange Commission issued thereunder with respect to any part of the Registration Statement, including this opinion as an exhibit or otherwise. This opinion may be used only in connection with the offer and sale of the Securities while the Registration Statement is effective.