Exhibit 5.1

[Schiff Hardin LLP Letterhead]

January 22, 2014

Board of Directors

Cytomedix, Inc.

209 Perry Parkway, Suite 7

Gaithersburg, MD 20877

Re:     Registration Statement on Form S-1

Gentlemen:

We have acted as counsel to Cytomedix, Inc., a Delaware corporation (the “Company”) in connection with the preparation and filing of the Registration Statement on Form S-1 (SEC Registration No. 333-193246) (the “Registration Statement”) filed by the Company with the United States Securities and Exchange Commission under the Securities Act of 1933, as amended (“Act”). The Registration Statement covers the resale by the selling stockholders listed in the Registration Statement of up to 13,082,408 shares of the Company’s common stock, par value $.0001 (the “Common Stock”), consisting of: (i) Common Stock issuable upon conversion of principal and interest under the 10% Subordinated Convertible Promissory Notes (the “Notes”) sold to the Selling Stockholders in December 2013 (the “Note Shares”), (ii) Common Stock underlying warrants sold in December 2013 (the “Warrants”) (the “Warrant Shares”), and (iii) Common Stock underlying warrants issued to the placement agent in connection in December 2013 (the “Placement Agent Warrants”) (the “Placement Agent Warrant Shares”).

In rendering this opinion, we have examined: (i) the Certificate of Incorporation and By-laws of the Company, each as presently in effect and included as Exhibits 3(i) and (ii), respectively, to the Registration Statement; (ii) resolutions of the Company’s Board of Directors authorizing the issuance of the Notes, the Warrants, the Placement Agent Warrants, the Notes Shares, the Warrant Shares and the Placement Agent Warrant Shares; (iii) the Registration Statement; (iv) the form of the Notes, (v) the form of the Warrants and the Placement Agent Warrants, and (vi) such statutory provisions, certificates and other documents as we have deemed appropriate or necessary as a basis for the opinions hereinafter expressed. We have also examined such other documents and considered such legal matters as we have deemed necessary and relevant as the basis for the opinion set forth below. With respect to such examination, we have assumed the genuineness of all signatures, the authenticity of all documents submitted to us as originals, the conformity to original documents of all documents submitted to us as reproduced or certified copies, and the authenticity of the originals of those latter documents.

Based upon the foregoing and in reliance thereon, subject to the limitations, assumptions and qualifications set forth herein, we are of the opinion that (i) the Note Shares, when issued by the Company upon conversion of the Notes in accordance with the terms of such Notes, will have been duly authorized, validly issued, fully paid and nonassessable, and (ii) the Warrant Shares and the Placement Agent Warrant Shares, when issued by the Company upon the exercise of the Warrants and the Placement Agent Warrants in accordance with the terms of such respective warrants, will have been duly authorized, validly issued, fully paid and nonassessable.

This opinion is limited to the Federal law of the United States and the General Corporation Law of the State of Delaware, and we express no opinion as to the laws of any other jurisdiction. This opinion is rendered pursuant to Item 601(b)(5)(i) of Regulation S-K under the Act. The opinions expressed in this opinion letter are as of the date of this opinion letter only and as to laws covered hereby only as they are in effect on that date, and we assume no obligation to update or supplement such opinions to reflect any facts or circumstances that may come to our attention after that date or any changes in law that may occur or become effective after that date. The opinions herein are limited to the matters expressly set forth in this opinion letter, and no opinion or representation is given or may be inferred beyond the opinions expressly set forth in this opinion letter.

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 the prospectus contained in the Registration Statement. In giving this consent, we do not thereby 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 Securities and Exchange Commission promulgated thereunder.

/s/ Schiff Hardin LLP