Exhibit 5.1

August 13, 2013

Roadrunner Transportation Systems, Inc.

4900 S. Pennsylvania Ave.

Cudahy, Wisconsin 53110

Dear Ladies and Gentlemen:

We have acted as special counsel to Roadrunner Transportation Systems, Inc., a Delaware corporation (the “Company”), in connection with the registration under the Securities Act of 1933, as amended (the “Securities Act”), of the offer and sale of up to an aggregate of 4,945,000 shares of the Company’s common stock, par value $0.01 per share (the “Shares”) (which includes 1,500,000 shares of common stock to be sold by the Company, 2,800,000 shares of common stock to be sold by selling stockholders, and an over-allotment option granted by the selling stockholders to the underwriters to purchase up to 645,000 additional shares of common stock to cover over-allotments, if any), pursuant to the terms of the Underwriting Agreement (the “Underwriting Agreement”), dated August 13, 2013, among the Company, the selling stockholders named therein, and Robert W. Baird & Co. Incorporated, Morgan Stanley & Co. LLC and Deutsche Bank Securities Inc., as representatives of the several underwriters named in Schedule II thereto. The Shares are being offered and sold under a Registration Statement on Form S-3 under the Securities Act originally filed with the Securities and Exchange Commission (the “Commission”) on August 10, 2011 (Registration No. 333-176225) (such Registration Statement, as amended and supplemented, the “Registration Statement”), including a base prospectus dated August 31, 2011 (the “Base Prospectus”), a preliminary prospectus supplement dated August 13, 2013 (the “Preliminary Prospectus Supplement”), and a final prospectus supplement dated August 13, 2013 (the “Final Prospectus Supplement,” and together with the Base Prospectus and the Preliminary Prospectus Supplement, the “Prospectus”).

With respect to the opinion set forth below, we have examined originals, certified copies, or copies otherwise identified to our satisfaction as being true copies of such documents, corporate records, certificates of public officials, and other instruments as we have deemed necessary for the purposes of rendering the opinion set forth herein.

For purposes of this opinion, we have assumed the authenticity of all documents submitted to us as originals, the conformity to the originals of all documents submitted to us as copies, and the authenticity of the originals of all documents submitted to us as copies. We have also assumed the legal capacity of all natural persons, the genuineness of the signatures of persons signing all documents in connection with which this opinion is rendered, the authority of such persons signing on behalf of the parties thereto other than the Company, and the due authorization, execution, and delivery of all documents by the parties thereto other than the Company. We have not independently established or verified any facts relevant to the opinions expressed herein, but have relied upon statements and representations of officers and other representatives of the Company and the selling stockholders.

Based solely upon and subject to the foregoing, and subject to the assumptions, limitations, and qualifications stated herein, we are of the opinion that (A) the portion of the Shares to be sold by the Company have been duly authorized and, when issued, delivered, and paid for in accordance with the terms of the Underwriting Agreement, will be validly issued, fully paid, and non-assessable; and (B) the portion of the Shares to be sold by the selling stockholders have been validly issued and are fully paid and non-assessable.

GREENBERG TRAURIG, LLP n ATTORNEYS AT LAW n WWW.GTLAW.COM

2375 East Camelback Road, Suite 700 n Phoenix, Arizona 85016 n Tel 602.445.8000 n Fax 602.445.8100

Roadrunner Transportation Systems, Inc.

August 13, 2013

Page 2

We render this opinion with respect to, and express no opinion herein concerning the application or effect of the law of any jurisdiction other than, the existing laws of the United States of America, and of the Delaware General Corporation Law, the Delaware Constitution, and reported judicial decisions relating thereto.

We hereby consent to the filing of this opinion letter as Exhibit 5.1 to the Company’s Current Report on Form 8-K to be filed on August 14, 2013 and to the reference to this firm under the caption “Legal Matters” in the Prospectus constituting a part of the Registration Statement. In giving this consent, we do not admit that we are experts within the meaning of Section 11 of the Securities Act or within the category of persons whose consent is required by Section 7 of the Securities Act.

Sincerely,

/s/ Greenberg Traurig, LLP

Greenberg Traurig, LLP