Exhibit 5.1

Paul, Weiss, Rifkind, Wharton & Garrison LLP

1285 Avenue of the Americas

New York, New York 10019-6064

212-373-3000

212-757-3990

June 18, 2007

Dice Holdings, Inc.

3 Park Avenue

33rd Floor

New York, New York 10016

Registration Statement on Form S-1

(Registration No. 333-141876)

Ladies and Gentlemen:

In connection with the Registration Statement on Form S-1, as amended (the “Registration Statement”) of Dice 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 to furnish our opinion as to the legality of the securities being registered under the Registration Statement. The Registration Statement relates to

2

the registration under the Act of (i) up to 6,700,000 shares (the “Primary Shares”) of the Company’s common stock, par value $0.01 per share (the “Common Stock”), that may be offered by the Company and (ii) up to 12,505,000 shares of Common Stock that may be offered by certain stockholders of the Company (including shares that may be sold by certain stockholders of the Company upon exercise of the underwriters’ over-allotment option) (the “Secondary Shares”).

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 form of the Underwriting Agreement (the “Underwriting Agreement”), included as Exhibit 1.1 to the Registration Statement;

3. the form of the Amended and Restated Certificate of Incorporation of the Company (the “Certificate of Incorporation”), included as Exhibit 3.1 to the Registration Statement;

4. the form of the Amended and Restated Bylaws of the Company, included as Exhibit 3.2 to the Registration Statement;

5. the form of Second Amended and Restated Shareholders Agreement, to be entered into by and among Dice Holdings, Inc. and the eFinancialGroup stockholders named therein, included as Exhibit 10.1 to the Registration Statement;

6. the form of Institutional and Management Shareholder Agreement, to be entered into by and among Dice Holdings, Inc., the Quadrangle entities named therein, the General Atlantic entities named therein and the management stockholders named therein, included as Exhibit 10.2 to the Registration Statement; and

3

7. the 2005 Omnibus Stock Plan of the Company (the “2005 Plan”) and certain option agreements relating to the options to purchase shares of Common Stock granted under the 2005 Plan (the “Option Agreements”).

In addition, we have examined (i) such corporate records of the Company that we have considered appropriate, including a copy of the certificate of incorporation, as amended, and by-laws, as amended, of the Company, certified by the Company as in effect on the date of this letter, the Certificate of the Powers, Designations, Preferences and Rights of the Series A Convertible Preferred Stock (the “Certificate of Designation”) and copies of resolutions of the board of directors of the Company relating to the issuance of the Primary Shares and the Secondary Shares, certified by the Company and (ii) 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 the factual matters contained in the representations and warranties of the Company made in the Documents 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 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. We have also assumed that (i) the Company and its stockholders will duly authorize the Certificate of Incorporation and the Company will duly file the Certificate of Incorporation with the

4

Secretary of State of Delaware in the form reviewed by us, (ii) in accordance with the terms of the Certificate of Designation, prior to the offering, the holders of 66 2/3% of all outstanding Series A convertible preferred stock will require that all of such outstanding shares be converted into an equal number of shares of Common Stock (the “Conversion”) and (iii) in respect of any Secondary Shares to be sold by selling stockholders upon the exercise of options to purchase Common Stock granted under the 2005 Plan, such selling stockholder will duly exercise their options prior to the offering.

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

1. The Primary Shares have been duly authorized by all necessary corporate action on the part of the Company and, when issued, delivered and paid for as contemplated in the Registration Statement and in accordance with the terms of the Underwriting Agreement, the Primary Shares will be validly issued, fully paid and non-assessable.

2. The Secondary Shares have been duly authorized by all necessary corporate action on the part of the Company and, after giving effect to the Conversion or after they are issued, delivered and paid for in accordance with the 2005 Stock Plan and Option Agreements, the Secondary Shares will be validly issued, fully paid and non-assessable.

The opinions expressed above are 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 and orders under those laws, that are currently in effect.

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

5

prospectus included in 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.

Very truly yours,

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