PAUL, WEISS, RIFKIND, WHARTON & GARRISON LLP

1285 Avenue of the Americas

New York, New York 10019

February 2, 2009

ExlService Holdings, Inc.

350 Park Avenue

New York, New York 10022

Ladies and Gentlemen:

In connection with the Registration Statement on Form S-8 (the “Registration Statement”) of ExlService Holdings, Inc., a Delaware corporation (the “Company”), filed with the Securities and Exchange Commission (the “Commission”) pursuant to the Securities Act of 1933, as amended (the “Act”), and the rules and regulations thereunder (the “Rules”), you have asked us to furnish our opinion as to the legality of securities being registered under the Registration Statement. The Registration Statement relates to the registration under the Act of 4,000,000 shares of Common Stock, par value $0.001 per share, of the Company (the “Shares”), issuable in respect of awards to be granted under the ExlService Holdings, Inc. 2006 Omnibus Award Plan (as amended to date, the “2006 Plan”).

In connection with the furnishing of this opinion, we have examined originals, or copies certified or otherwise identified to our satisfaction, of the following documents (collectively, the “Documents”):

1. the Registration Statement;

2. the 2006 Plan and the forms of option agreement and restricted stock award agreement (collectively, the “Agreements”) relating to options to purchase, or other awards to acquire, Shares granted under the 2006 Plan.

3. the Amended and Restated Certificate of Incorporation of the Company, included as Exhibit 3.1 to the Company’s Current Report on Form 8-K filed with the Commission on October 25, 2006; and

4. the Second Amended and Restated Bylaws of the Company, included as Exhibit 3.1 to the Company’s Current Report on Form 8-K filed with the Commission on April 30, 2008.

In addition, we have examined such corporate records of the Company that we have considered appropriate and such other certificates, agreements and documents that we deemed relevant and necessary as a basis for the opinions expressed below. We have also relied upon certificates of public officials and officers of the Company.

In our examination of the documents referred to above, we have assumed, without independent investigation, the genuineness of all signatures, the legal capacity of all individuals who have executed any of the documents reviewed by us, the authenticity of all documents submitted to us as originals, the conformity to the originals of all documents submitted to us as certified, photostatic, reproduced or conformed copies of valid existing agreements or other documents, the authenticity of all the latter documents and that the statements regarding matters of fact in the certificates, records, agreements, instruments and documents that we have examined are accurate and complete.

Based upon the above, and subject to the stated qualifications, we are of the opinion that, when issued in accordance with the terms of the 2006 Plan and any applicable Agreement under the Plans, the Shares will be duly authorized, validly issued, fully paid and non-assessable.

The opinion expressed above is limited to the General Corporation Law of the State of Delaware. Our opinion is rendered only with respect to the laws, and the rules, regulations, orders and applicable judicial and regulatory determinations under those laws, that are currently in effect.

We hereby consent to use of this opinion as an exhibit to the Registration Statement. In giving this consent, we do not thereby admit that we come within the category of persons whose consent is required by the Act or the Rules.