Exhibit 10.1

EMPLOYMENT AGREEMENT

THIS EMPLOYMENT AGREEMENT (this “Agreement”) is effective as of the 9th day of February, 2009, by and between Nadine Teixeira (“Employee”) and CAI International, Inc., a Delaware corporation (the “Company”). In consideration of the mutual covenants herein contained, and in consideration of the continued employment of Employee by the Company, the parties agree as follows:

1. Duties and Scope of Employment.

(a) Position. The Company agrees to employ the Employee for the term of her employment under this Agreement in the position of Director of International Legal Affairs on the terms and conditions set forth in this Agreement. In this position Employee is a corporate attorney with extensive international experience who shall assume the role of the Company’s counsel in regards to the Company’s international legal matters related to the Company’s core business, including but not limited to drafting, revising and where appropriate negotiating (from a legal perspective): (i) container management agreements, master lease agreements, precautionary assignment of leases, step-in-right agreements and other documents related to the purchase, sale and management of shipping containers; and (ii) manufacturing agreements with foreign container manufacturers. In addition, Employee shall interface and work with the Company’s outside counsel in connection with matters of foreign law and international mergers and acquisitions. It is understood and agreed, however, that Employee is not the Company’s general counsel. Accordingly, unless specifically directed by the Company’s executive officers or Board of Directors, Employee shall not have responsibility for advising the Board of Directors, setting legal policy, managing litigation, hiring, firing or directing the work of outside counsel, or other matters that are customarily the purview of the chief legal officer of a company.

(b) Flexible Hours. Employee’s normal work schedule shall be at the offices of the Company from 9:30 AM – 4:30 PM each Monday, Wednesday and Friday and 9:00 AM – 2:00 PM on Tuesdays and Thursdays. It is understood that Employee is an “exempt” employee (for purposes of overtime compensation) and Employee’s responsibilities are not limited to normal working hours. When she is not working from the Company’s office, Employee shall be reasonably available to assist on projects as needed, through remote internet connection and through her cellular telephone. Notwithstanding anything to the contrary contained herein, Employee understands and agrees that her job duties may require that she work more than 40 hours per week from time to time, which may include some travel.

(c) Reporting. As such counsel, Employee shall report directly to Mr. Victor Garcia, the Company’s Chief Financial Officer, and shall be responsible for such legal and other matters as may be assigned to her by Mr. Garcia or by the Company’s Chief Executive Officer or Executive Chairman.

(d) Obligations. During the term of her employment under this Agreement, the Employee shall be responsible for such legal matters as are assigned to her from time to time, and shall perform and discharge well and faithfully her duties and shall devote her full business efforts and time to the Company. The foregoing, however, shall not preclude the Employee from engaging in appropriate civic or charitable activities or from serving on the boards of directors of other noncommercial entities, as long as such activities and service do not interfere or conflict with her responsibilities to the Company.

2. Salary and Bonus.

(a) Base Salary. During her employment under this Agreement, the Company agrees to pay to the Employee as compensation for her services, effective February 9, 2009 (the “Effective Date”), a base salary (“Base Salary”) at an initial annual rate of $204,000, payable in twenty-four (24) equal bi-monthly installments.

(b) Bonus. Employee shall also be eligible for a discretionary annual cash bonus, not to exceed forty percent (40%) of Base Salary. Any amounts due to the Employee as a cash bonus shall be paid not later than the one hundred and twentieth (120th) day of the calendar year immediately following the fiscal year to which such bonus relates.

3. Employee Benefits.

(a) General. During the term of her employment under this Agreement, the Employee and her spouse and children shall be eligible to participate in the employee benefit plans made available by the Company to its Vice Presidents generally, including (without limitation) any of the following plans if and when adopted and made available by the Board of Directors: health, vision and dental insurance, pension plans, savings plans, deferred compensation plans, life, disability, accident and other insurance programs, and similar plans or programs subject in each case to the generally applicable terms and conditions of the plan in question and to the determination of any committee administering such plan or program.

(b) Death and Disability. Subject to the Employee’s insurability, the Company will enroll Employee in (a) the Company’s policy of long-term disability insurance, with the Employee named as the direct beneficiary and (b) the Company’s term life insurance policy (currently providing a benefit of $500,000 upon death of a covered employee) with an annual premium not to exceed Four Thousand Dollar ($4,000) annual.

(c) Vacation. The Employee shall be entitled to paid vacation accruing at the rate of sixteen (16) business days per year. Unused vacation for any year shall not carry over into subsequent years.

(d) Visa and Green Card Expenses. The Company will reimburse Employee for the cost of transfer of Employee’s current H1B Visa and for Employee’s Green Card. The Company will also reimburse the cost of Visa expense for Employee’s immediate family, to permit her immediate family to permanently reside in the United States. Employee may select the counsel to handle the Visa and Green Card legal work, which counsel shall be reasonably acceptable to the Company and shall be directly retained by the Company for this purpose. The aggregate cost of Visa and Green Card expenses for Employee and her family shall not exceed Twenty Thousand Dollars ($20,000).

-2-

(e) Bar Dues. Company will reimburse Employee for her annual California State Bar dues, as well as the cost of annual membership in the American Bar Association.

(f) Parking. The Company will provide Employee with a parking space near the Company’s place of business in San Francisco, which, if available, shall be in One Embarcadero Center.

4. Term of Employment.

(a) Basic Rule. Unless Employee’s employment terminates at an earlier date pursuant to the provisions of this Agreement, the Company agrees to continue Employee’s employment on the terms set forth herein, and Employee agrees to remain in the employ of the Company, beginning on the Effective Date until February 9, 2011. Notwithstanding the foregoing, Employee and the Company agree that the Employee is an employee at will, and Employee’s employment may be terminated by the Employee or the Company at any time for any reason (or for no reason at all). However, except for termination for “Cause” (as hereinafter defined), the Company shall provide Employee with at least thirty (30) days prior notice of any termination.

(b) Severance Benefits on a Change of Control or if Termination is without “Cause”. Notwithstanding the foregoing, if Employee elects to terminate her employment within thirty (30) days following a “Change of Control” (as hereinafter defined) or the Company terminates Employee without “Cause” (as hereinafter defined), Employee shall be entitled to the following severance benefits

(i) Severance Payment. The Company shall pay the Employee an amount equal to 100% of Employee’s base salary as in effect on the date of termination for a period of six (6) months, to be paid within 30 days after the date of termination or Change of Control; .

(ii) Continuation of Insurance. The Company will reimburse Employee for a continuation of health, vision and dental insurance benefits for herself and her immediate family for a period of up to six (6) months as provided to Employee immediately prior to termination; provided that if Employee opts to return to Brazil, the Company shall not be obligated to continue to reimburse the cost of these benefits for the period after Employee leaves the United States.

(iii) Relocation Expense. If: (i) termination occurs prior to issuance of a Green Card to Employee; and (ii) Employee opts to return to Brazil within the severance period, the Company shall reimburse Employee for up to Twenty Five Thousand Dollars ($25,000) of relocation expense for the cost of relocating Employee and her family to Brazil.

(iv) No Duty to Mitigate. Employee shall not be required to mitigate the amount of any payment contemplated under this Section 4(b), whether Employee seeks new employment or in any other manner, nor shall any payment under this Section 4(b) be reduced by any earnings that Employee may receive from any other source.

-3-

(c) Definitions of “Change of Control” and “Cause”

(i) Change of Control. For purposes of this Agreement, “Change of Control” shall have the following meaning: (i) merger or consolidation of the Company with or into any other company or other entity, other than for the sole purpose of changing the Company’s state of incorporation); (ii) a sale in one transaction or a series of transactions undertaken with a common purpose of all or a majority of the Company’s outstanding voting securities or such amount of the Company’s outstanding voting securities as would enable the purchaser to obtain the right to appoint a majority of the Company’s Board of Directors; and (iii) a sale, lease, exchange or other transfer in one transaction or a series of related transactions undertaken with a common purpose of all or substantially all of the Company’s assets. Notwithstanding the foregoing, a transaction in which Mr. Hiromitsu Ogawa (and his affiliates) gain a majority of the Company’s voting stock or the ability to appoint a majority of the Company’s board of directors shall not constitute a Change of Control.

(ii) Cause. For purposes of this Agreement, “Cause” shall mean:

(A) A failure by the Employee to substantially perform her duties hereunder which is not cured within thirty (30) days after notice from the Company;

(B) An act by the Employee of dishonesty, fraud, misrepresentation, or other act(s) of moral turpitude;

(C) An intentional act by the Employee (other than one constituting a legal judgment that was reasonable at the time), or a clear lack of reasonable care by the Employee, or gross misconduct by the Employee, which (in each case) is seriously injurious to the Company;

(D) A material breach by the Employee of this Agreement which is not cured within thirty (30) days after notice from the Company; or

(E) A material or willful violation of a federal or state law or regulation applicable to the business of the Company; or

(F) Employee, due to lack of a proper Visa or work permit, or for any other reason, is unable to legally be employed in the State of California.

(d) Benefits Payable Upon Constructive Termination

The severance benefits listed under Sections 4(b) (i) and (ii) shall also be paid by the Company to Employee in the event Employee terminates her employment under circumstances which constitutes a “Constructive Termination.” For purposes of this Agreement, “Constructive Termination shall mean any of the following events:

(A) any material breach by the Company of this Agreement;

-4-

(B) without the Employee’s written consent, a material change in the geographic location at which Employee must perform her duties under this Agreement, except for office relocation within the San Francisco Bay area; provided that Employee hereby acknowledges and agrees that she may be required to travel in connection with the performance of her duties under this Agreement and that any such travel requirement will not constitute a material change in the geographic location at which Employee must perform her duties under this Agreement.;

(C) without Employee’s consent, any material and adverse change to the Employee’s job description under Section 1(a) above.

Notwithstanding any provision in this Agreement to the contrary, termination of Employee’s employment will not constitute a Constructive Termination unless (i) Employee notifies the Company in writing of the existence of the condition which Employee believes constitutes Constructive Termination within ninety (90) days of the initial existence of such condition (which notice specifically identifies such condition), (ii) the Company fails to remedy such condition within thirty (30) days after the date on which it receives such notice (the “Remedial Period”), and (iii) Employee actually terminates employment within thirty (30) days after the expiration of the Remedial Period and before the Company remedies such condition. If Employee terminates employment before the expiration of the Remedial Period or after the Company remedies the condition (even if after the end of the Remedial Period), then Employee’s termination will not be considered a Constructive Termination. Notwithstanding the foregoing, if at the time Employee terminates her employment with the Company under the circumstances described above in this Section 4(d) and any of the circumstances described in Section 4(c)(ii) then exist, then Employee’s employment shall be deemed to have been terminated by the Company pursuant to Section 4(e) rather than pursuant to this Section 4(d) for all purposes of this Agreement.

(e) Benefits Payable Upon Other Terminations. In the event Employee’s employment is terminated (or deemed terminated) by the Company for Cause or Employee terminates her employment other than pursuant to Section 4(b) or Section 4(d), Employee shall be entitled to all accrued compensation and all other accrued benefits through the effective date of termination, but shall not be entitled to any other compensation or benefits, and shall not be entitled to any bonus under Section 2(b) for the fiscal year in which the termination occurs. All accrued compensation and all other accrued benefits shall be paid to Employee within thirty (30) days after the date on which Employee’s employment with the Company terminates.

5. Proprietary Information.

The Employee agrees, during and after the term of her employment by the Company, to comply fully with the Company’s policies relating to non-disclosure of the Company’s trade secrets and proprietary information and processes and hereby acknowledges and re-affirms her obligations to the Company pursuant to the Employment, Confidential Information and Intellectual Property Assignment Agreement executed by the Employee with the Company.

-5-

6. Section 280G

(a) Notwithstanding anything to the contrary herein, Section 6(b) shall apply in the event that the Company satisfies the requirement of Section 280G(b)(5)(A)(ii)(I) of the Code. In the event that the Company does not satisfy such requirement, Section 6(c), not Section 6(b), shall apply.

(b) Prior to any change described in Section 280G(b)(2)(A)(i) of the Code (a “Section 280G Transaction”) and in accordance with the requirements of Section 280G(b)(5)(B) of the Code, the Company shall seek, but shall not be required to obtain, approval by its shareholders of any payments, options, awards or benefits (including, without limitation, the monetary value of any non-cash benefits and the accelerated vesting of stock options) under this Agreement or under any other plan, agreement or arrangement with the Company, any person whose actions result in a Section 280G Transaction or any person affiliated with the Company or such person (collectively, the “Payments”), that may separately or in the aggregate constitute “parachute payments” within the meaning of Section 280G (collectively, the “Potential Parachute Payments”). In the event that the shareholders of the Company do not approve the Employee’s Potential Parachute Payments in accordance with Section 280G(b)(5)(B) of the Code, the Employee will have no right or entitlement to receive or retain, as the case may be, that portion of her Potential Parachute Payments that would otherwise cause any portion of any of her Potential Parachute Payments to be treated as an “excess parachute payment” (within the meaning of Section 280G).

(c) In the event that the Employee becomes entitled to receive or receives any Payments and it is determined that, but for this Section 6(c), any of the Payments will be subject to any excise tax pursuant to Section 4999 of the Code or any similar or successor provision (the “Excise Tax”), the Company shall pay to the Employee either (i) the full amount of the Payments or (ii) an amount equal to the Payments, reduced by the minimum amount necessary to prevent any portion of the Payments from being an “excess parachute payment” (within the meaning of Section 280G) (the “Capped Payments”), whichever of the foregoing amounts results in the receipt by the Employee, on an after-tax basis, of the greatest amount of Payments notwithstanding that all or some portion of the Payments may be subject to the Excise Tax. For purposes of determining whether an Employee would receive a greater after-tax benefit from the Capped Payments than from receipt of the full amount of the Payments, (i) there shall be taken into account any Excise Tax and all applicable federal, state and local taxes required to be paid by the Employee in respect of the receipt of such payments and (ii) such payments shall be deemed to be subject to federal income taxes at the highest rate of federal income taxation applicable to individuals that is in effect for the calendar year in which the benefits are to be paid, and state and local income taxes at the highest rate of taxation applicable to individuals in the state and locality of the Employee’s residence on the effective date of the Section 280G Transaction, net of the maximum reduction in federal income taxes which could be obtained from deduction of such state and local taxes (as determined by assuming that such deduction is subject to the maximum limitation applicable to itemized deductions under Section 68 of the Code and any other limitations applicable to the deduction of state and local income taxes under the Code).

-6-

(d) All calculations and determinations under this Section 6, including application and interpretation of the Code and related regulatory, administrative and judicial authorities, shall be made by an independent accounting firm or independent tax counsel appointed by the Company (the “Tax Advisor”). All determinations made by the Tax Advisor under this Section 6 shall be conclusive and binding on both the Company and the Employee, and the Company shall cause the Tax Advisor to provide its determinations and any supporting calculations with respect to the Employee to the Company and the Employee. The Company shall bear all fees and expenses charged by the Tax Advisor in connection with its services. For purposes of making the calculations and determinations under this Section 6, after taking into account the information provided by the Company and the Employee, the Tax Advisor may make reasonable, good faith assumptions and approximations concerning the application of Sections 280G and 4999 of the Code. The Company and the Employee shall furnish the Tax Advisor with such information and documents as the Tax Advisor may reasonably request to assist the Tax Advisor in making calculations and determinations under this Section 6. In the event that Section 6(c) applies and a reduction is required to be applied to the Payments thereunder, the Payments shall be reduced by the Company in its reasonable discretion in the following order: (i) reduction of any Payments that are subject to Section 409A of the Code on a pro-rata basis or such other manner that complies with Code Section 409A, as determined by the Company, and (ii) reduction of any Payments that are exempt from Code Section 409A.

(e) Definitions. For purposes of this Agreement, the following terms shall have the following meanings:

(i) “Code” shall mean the Internal Revenue Code of 1986, as amended, and the Treasury regulations promulgated thereunder.

(ii) “Section 280G” shall mean Section 280G of the Code and the Treasury regulations promulgated thereunder or any similar or successor provision.

-7-

7. Section 409A

The Company makes no representations or warranties to Employee with respect to any tax, economic or legal consequences of this Agreement or any payments or other benefits provided hereunder, including without limitation under Section 409A of the Code, and no provision of the Agreement shall be interpreted or construed to transfer any liability for failure to comply with Code Section 409A or any other legal requirements from Employee or any other individual to the Company or any of its affiliates. Employee, by executing this Agreement, shall be deemed to have waived any claim against the Company and its affiliates with respect to any such tax, economic and legal consequences. However, the parties intend that this Agreement and the payments and other benefits provided hereunder be exempt from the requirements of Code Section 409A to the maximum extent possible, whether pursuant to the short-term deferral exception described in Treasury Regulation Section 1.409A-1(b)(4), the involuntary separation pay plan exception described in Treasury Regulation Section 1.409A-1(b)(9)(iii), or otherwise. To the extent Code Section 409A is applicable to this Agreement (and such payments and benefits), the parties intend that this Agreement (and such payments and benefits) comply with the deferral, payout and other limitations and restrictions imposed under Code Section 409A. Notwithstanding any other provision of this Agreement to the contrary, this Agreement shall be interpreted, operated and administered in a manner consistent with such intentions. Without limiting the generality of the foregoing, and notwithstanding any other provision of this Agreement to the contrary, with respect to any payments and benefits under this Agreement to which Code Section 409A applies, all references in this Agreement to the termination of Employee’s employment are intended to mean Employee’s “separation from service,” within the meaning of Code Section 409A(a)(2)(A)(i). In addition, if Employee is a “specified employee,” within the meaning of Code Section 409A(a)(2)(B)(i), then to the extent necessary to avoid subjecting Employee to the imposition of any additional tax under Code Section 409A, amounts that would otherwise be payable under this Agreement during the six-month period immediately following Employee’s “separation from service,” within the meaning of Section 409A(a)(2)(A)(i) of the Code, shall not be paid to Employee during such period, but shall instead be accumulated and paid to Employee (or, in the event of Employee’s death, Employee’s estate) in a lump sum on the first business day following the earlier of (a) the date that is six months after Employee’s separation from service or (b) Employee’s death.

8. Successors.

(a) Company’s Successors. Any successor to the Company (whether direct or indirect and whether by purchase, lease, merger, consolidation, liquidation or otherwise) to all or substantially all of the Company’s business and/or assets shall assume this Agreement and agree expressly to perform this Agreement in the same manner and to the same extent as the Company would be required to perform it in the absence of a succession. For all purposes under this Agreement, the term “Company” shall include any successor to the Company’s business and/or assets which executes and delivers the assumption agreement described in this subsection (a) or which becomes bound by this Agreement by operation of law.

-8-

(b) Employee’s Successors. This Agreement and all rights of the Employee hereunder shall inure to the benefit of, and be enforceable by, the Employee’s personal or legal representatives, executors, administrators, heirs, distributees, devisees and legatees.

9. Notice.

Notices and all other communications contemplated by this Agreement shall be in writing and shall be deemed to have been duly given when personally delivered or when mailed by U.S. registered or certified mail, return receipt requested and postage prepaid. In the case of the Employee, mailed notices shall be addressed to him at the home address which he most recently communicated to the Company in writing. In the case of the Company, mailed notices shall be addressed to its corporate headquarters, and all notices shall be directed to the attention of its Secretary.

10. Miscellaneous Provisions.

(a) Waiver. No provision of this Agreement shall be modified, waived or discharged unless the modification, waiver or discharge is agreed to in writing and signed by the Employee and by authorized officer of the Company (other than the Employee). No waiver by either party of any breach of, or of compliance with, any condition or provision of this Agreement by the other party shall be considered a waiver of any other condition or provision or of the same condition or provision at another time.

(b) Whole Agreement. No agreements, representations or understanding (whether oral or written and whether express or implied) which are not expressly set forth in this Agreement have been made or entered into by either party with respect to the subject matter hereof.

(c) Choice of Law. The validity, interpretation, construction and performance of this Agreement shall be governed by the laws of the State of California.

(d) Severability. The invalidity or enforceability of any provision or provisions of this Agreement shall not affect the validity or enforceability of any other provision hereof, which shall remain in full force and effect.

(e) No Assignment of Benefits. The rights of any person to payments or benefits under this Agreement shall not be made subject to option or assignment, either by voluntary or involuntary assignment or by operation of law, including (without limitation) bankruptcy, garnishment, attachment or other creditor’s process, and any action in violation of this subsection (e) shall be void.

(f) Limitation of Remedies. If the Employee’s employment hereunder terminates for any reason, the Employee shall not be entitled to any payments, benefits, damages, awards or compensation other than as provided by this Agreement.

-9-

(g) Withholding. The Company shall be entitled to deduct and withhold from any amounts payable under this Agreement such amounts as the Company is required to deduct or withhold therefrom under the Code or under any other applicable law.

(h) Captions. Captions contained herein are inserted only as a matter of convenience and in no way define, limit or extend the scope or intent of any provision hereof.

(i) Counterparts. This Agreement may be executed in counterparts, each of which shall be deemed an original, but all of which together will constitute one and the same instrument.

(j) Arbitration. Any dispute or claim arising under or relating to this Agreement (including without limitation the validity or scope of this Agreement or of any provision hereof or of this Section 10(j)) shall be determined exclusively by arbitration before a single arbitrator in accordance with the commercial arbitration rules of the American Arbitration Association. In the event the parties cannot agree on an arbitrator within 10 days after either party makes a written call for arbitration hereunder, the arbitrator shall be appointed by the Executive Director of the Northern California office of the American Arbitration Association.

-10-

IN WITNESS WHEREOF, each of the parties has executed this Agreement, in the case of the Company by its duly authorized officer, as of the day and year first above written.

-11-