Exhibit 5.1

August 10, 2018

CAI International, Inc.

Steuart Tower, 1 Market Plaza, Suite 900

San Francisco, California 94105

Re: CAI International, Inc.—Registration Statement on Form S-3 (File No. 333-217915)

Ladies and Gentlemen:

We have acted as counsel to CAI International, Inc., a Delaware corporation (the “Company”), in connection with the preparation and filing with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Securities Act”), of the registration statement on Form S-3 (File No. 333-217915) (the “Registration Statement”), including the prospectus which forms a part of the Registration Statement (the “Base Prospectus”), and the prospectus supplement dated August 6, 2018 filed with the Commission pursuant to Rule 424(b) under the Securities Act (the “Prospectus Supplement” and, together with the Base Prospectus, the “Prospectus”) with respect to the issuance and sale by the Company of up to 1,955,000 shares (the “Shares”) of the Company’s 8.50% Series B Fixed-to-Floating Rate Cumulative Redeemable Perpetual Preferred Stock, par value $0.0001 per share (the “Series B Preferred Stock”), which amount includes 255,000 shares of Series B Preferred Stock that may be sold by the Company to the underwriters pursuant to their option to purchase additional shares of Series B Preferred Stock. The Shares are being sold pursuant to the terms of an underwriting agreement, which is referred to in the Prospectus, by and between the Company and RBC Capital Markets, LLC, as representative of the several underwriters named therein (the “Underwriting Agreement”). The terms of the Series B Preferred Stock are set forth in a certificate of designations filed by the Company with the Secretary of State of the State of Delaware on August 10, 2018 (the “Certificate of Designations”).

We have examined the Registration Statement, the Prospectus, the Underwriting Agreement, the Certificate of Designations and such documents and records of the Company and other documents as we have deemed necessary for the purposes of this opinion. In such examination, we have assumed the following: (i) the authenticity of original documents and the genuineness of all signatures; (ii) the conformity to the originals of all documents submitted to us as copies; (iii) the truth, accuracy and completeness of the information, representations and warranties contained in the records, documents, instruments and certificates we have reviewed; and (iv) the effectiveness of the Registration Statement.

Based upon the foregoing, we are of the opinion that the Shares have been duly authorized by all necessary corporate action of the Company and, when issued and delivered in accordance with the terms of the Underwriting Agreement against payment of the consideration set forth therein, the Shares will be validly issued, fully paid and non-assessable.

We hereby consent to the filing of this opinion as Exhibit 5.1 to the Company’s Current Report on Form 8-K filed with the Commission on or about the date hereof, to the incorporation by reference of this opinion into the Registration Statement and any amendments thereto, including any and all post-effective amendments, and to the reference to us under the headings “Legal Matters” in the Prospectus. In giving such consent, we do not thereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act or related rules and regulations of the Commission issued thereunder.