Exhibit 5.1

Paul, Weiss, Rifkind, Wharton & Garrison LLP

1285 Avenue of the Americas

New York, New York 10019-6064

January 31, 2012

ExlService Holdings, Inc.

280 Park Avenue, 38^th Floor

New York, New York 10017

Registration Statement on Form S-3 (File No. 333-179098)

Ladies and Gentlemen:

In connection with the above-referenced Registration Statement on Form S-3 (the “Registration Statement”) of ExlService Holdings, Inc., a Delaware corporation (the “Company”), filed with the Securities and Exchange Commission pursuant to the Securities Act of 1933, as amended (the “Act”), and the rules and regulations thereunder (the “Rules”), you have asked us, as outside counsel to the Company, to furnish our opinion as to the legality of the securities being registered under the Registration Statement. The Registration Statement relates to the registration under the Act of the following securities of the Company (together, the “Securities”):

1. senior debt securities (the “Company Senior Debt Securities”) and subordinated debt securities (the “Company Subordinated Debt Securities” and, together with the Company Senior Debt Securities, the “Company Debt Securities”);

2. shares of preferred stock (including shares issued upon conversion of the Company Debt Securities or upon the exercise of warrants or purchase contracts) of the Company, par value $0.001 per share (the “Company Preferred Stock”);

3. shares of common stock (including shares issuable upon conversion or exchange of the Company Debt Securities or Company Preferred Stock or upon the exercise of warrants, rights or purchase contracts) of the Company, par value $0.001 per share (the “Company Common Stock”);

4. 6,552,504 shares of common stock of the Company, par value $0.001 per share, that may be offered by certain stockholders of the Company (the “Selling Stockholder Common Stock”);

5. depositary shares representing a fractional share or multiple shares of Company Preferred Stock evidenced by depositary receipts (the “Company Depositary Shares”);

6. warrants to purchase Company Debt Securities, Company Preferred Stock, Company Common Stock, Company Depositary Shares or any combination of them (the “Company Warrants”);

7. rights to purchase Company Common Stock (the “Company Rights”);

8. purchase contracts representing the Company’s obligation to sell Company Debt Securities, Company Preferred Stock, Company Common Stock, Depositary Shares, Company Warrants or government securities (the “Company Purchase Contracts”); and

9. units consisting of any combination of two or more of Company Debt Securities, Company Preferred Stock, Company Common Stock, Company Depositary Shares, Company Warrants, Company Purchase Contracts or debt obligations of third parties, including government securities (the “Company Units”).

The Securities are being registered for offering and sale from time to time as provided by Rule 415 under the Act.

The Company Senior Debt Securities are to be issued under an indenture to be entered into by and among the Company and U.S. Bank National Association, as trustee (the “Company Senior Debt Indenture”). The Company Subordinated Debt Securities are to be issued under an indenture to be entered into by and among the Company and U.S. Bank National Association, as trustee (the “Company Subordinated Debt Indenture” and, together with the Company Senior Debt Indenture, the “Company Indentures”).

The Company Depositary Shares are to be issued under deposit agreements, each between the Company and a depositary to be identified in the applicable agreement (each, a “Depositary Agreement”). The Company Warrants are to be issued under warrant agreements, each between the Company and a warrant agent to be identified in the applicable agreement (each, a “Warrant Agreement”). The Company Rights are to be issued under rights agreements, each between the Company and a rights agent to be identified in the applicable agreement (each, a “Rights Agreement”). The Company Purchase Contracts will be issued under purchase contract agreements, each between the Company and a purchase contract agent to be identified in the applicable agreement (each, a “Purchase Contract Agreement”). The Company Units are to be issued under unit agreements, each between the Company and a unit agent to be identified in the applicable agreement (each, a “Unit Agreement”).

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:

1. the Registration Statement; and

2. the forms of the Company Senior Debt Indenture and the Company Subordinated Debt Indenture (including the form of Securities included therein) incorporated by reference as Exhibits 4.1 and 4.2, respectively, to the Registration Statement.

In addition, we have examined (i) such corporate records of the Company as we have considered appropriate, including a copy of the certificate of incorporation, as amended, and by-laws, as amended, of the Company, and copies of resolutions of the board of directors of the Company and (ii) such other certificates, agreements and documents as we deemed relevant and necessary as a basis for the opinions expressed below. We have also relied upon the factual matters contained in the representations and warranties of the Company made in the documents reviewed by us and upon certificates of public officials and the 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 such 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.

We have also assumed, without independent investigation, that (i) the Company Indentures will be duly authorized, executed and delivered by the parties to them in substantially the forms incorporated by reference as exhibits to the Registration Statement, (ii) each of the Depositary Agreements, the Warrant Agreements, the Rights Agreements, the Purchase Contract Agreements, the Unit Agreements and any other agreement entered into, or officer’s certificates or board resolutions delivered, in connection with the issuance of the Securities will be duly authorized, executed and delivered by the parties to such agreements (such agreements and documents, together with the Company Indentures, are referred to collectively as the “Operative Agreements”), (iii) each Operative Agreement, when so authorized, executed and delivered, will be a valid and legally binding obligation of the parties thereto (other than the Company), (iv) the Company Depositary Shares, the Company Warrants, the Company Rights, the Company Purchase Contracts, the Company Units and any related Operative Agreements will be governed by the laws of the State of New York and (v) in the case of Company Purchase Contracts or Company Units consisting at least in part of debt obligations of third parties, such debt obligations at all relevant times constitute the valid and legally binding obligations of the issuers thereof enforceable against the issuers thereof in accordance with their terms.

With respect to the Securities of a particular series or issuance, other than the Selling Stockholder Common Stock, we have assumed that (i) the issuance, sale, number or amount, as the case may be, and terms of the Securities to be offered from time to time will be duly authorized and established, in accordance with the organizational documents of the Company, the laws of the State of New York and its jurisdiction of incorporation, and any applicable Operative Agreement, (ii) prior to the issuance of a series of Company Preferred Stock, an appropriate certificate of designation or board resolution relating to such series of Company Preferred Stock will have been duly authorized by the Company and filed with the Secretary of State of Delaware, (iii) the Securities will be duly authorized, executed, issued and delivered by the Company, and, in the case of Company Debt Securities, Company Depositary Shares, Company Warrants, Company Rights, Company Purchase Contracts and Company Units, duly authenticated or delivered by the applicable trustee or agent, in each case, against payment by the purchaser at the agreed-upon consideration, and (iv) the Securities will be issued and delivered as contemplated by the Registration Statement and the applicable prospectus supplement.

Based upon the above, and subject to the stated assumptions, exceptions and qualifications, we are of the opinion that:

1. When the specific terms of a particular issuance of Company Debt Securities (including any Company Debt Securities duly issued upon exercise, exchange or conversion of any Security in accordance with its terms) have been duly authorized by the Company and such Company Debt Securities have been duly executed, authenticated, issued and delivered, and, if applicable, upon exercise, exchange or conversion of any Security in accordance with its terms, such Company Debt Securities will be valid and legally binding obligations of the Company enforceable against the Company in accordance with their terms.

2. Upon due authorization by the Company of the issuance and sale of shares of a series of Company Preferred Stock, and, if applicable, upon exercise, exchange or conversion of any Security in accordance with its terms, such shares of Company Preferred Stock will be validly issued, fully paid and non-assessable.

3. Upon due authorization by the Company of the issuance and sale of shares of Company Common Stock, and, if applicable, upon exercise, exchange or conversion of any Security in accordance with its terms, such shares of Company Common Stock will be validly issued, fully paid and non-assessable.

4. The shares of Selling Stockholder Common Stock have been duly authorized by all necessary corporate action on the part of the Company and are validly issued, fully paid and non-assessable.

5. When any Company Depositary Shares evidenced by depositary receipts are issued and delivered in accordance with the terms of a Depositary Agreement against the deposit of duly authorized, validly issued, fully paid and non-assessable shares of Company Preferred Stock, such Company Depositary Shares will be valid and legally binding obligations of the Company and will entitle the holders thereof to the rights specified in the Depositary Agreement.

6. When the specific terms of a particular issuance of Company Warrants have been duly authorized by the Company and such Company Warrants have been duly executed, authenticated, issued and delivered, such Company Warrants will be valid and legally binding obligations of the Company enforceable against the Company in accordance with their terms.

7. When the specific terms of a particular issuance of Company Rights have been duly authorized by the Company and such Company Rights have been duly executed, authenticated, issued and delivered, such Company Rights will be valid and legally binding obligations of the Company enforceable against the Company in accordance with their terms.

8. When any Company Purchase Contracts have been duly authorized, executed and delivered by the Company, such Company Purchase Contracts will be valid and legally binding obligations of the Company enforceable against the Company in accordance with their terms.

9. When any Company Units have been duly authorized, issued and delivered by the Company, such Company Units will be valid and legally binding obligations of the Company enforceable against the Company in accordance with their terms.

The opinions expressed above as to enforceability may be subject to (i) bankruptcy, insolvency, reorganization, fraudulent conveyance or transfer, moratorium or similar laws affecting creditors’ rights generally, (ii) general principles of equity (regardless of whether enforceability is considered in a proceeding in equity or at law) and (iii) requirements that a claim with respect to any Securities in denominations other than in United States dollars (or a judgment denominated other than into United States dollars in respect of the claim) be converted into United States dollars at a rate of exchange prevailing on a date determined by applicable law.

The opinions expressed above are limited to the laws of the State of New York and the Delaware General Corporation Law.

We hereby consent to use of this opinion as an exhibit to the Registration Statement and to the use of our name under the heading “Legal Matters” contained in the prospectus included in the Registration Statement. In giving this consent, we do not hereby admit that we come within the category of persons whose consent is required by the Act or the Rules.

Very truly yours,

/s/ Paul, Weiss, Rifkind, Wharton & Garrison LLP

PAUL, WEISS, RIFKIND, WHARTON & GARRISON LLP