EXHIBIT 5.1

GIBSON, DUNN & CRUTCHER LLP
Lawyers

A REGISTERED LIMITED LIABILITY PARTNERSHIP
INCLUDING PROFESSIONAL CORPORATIONS

1050 Connecticut Avenue, N.W., Washington, D.C. 20036-5306
(202) 955-8500
www.gibsondunn.com

December 6, 2005

Direct Dial

(202) 955-8500

Fax No.

(202) 467-0539

NeuStar, Inc.
46000 Center Oak Plaza
Sterling, Virginia 20166

Re: NeuStar, Inc. — Registration Statement — on Form S-1 filed pursuant to Rule 462(b)

Ladies and Gentlemen:

     We have examined the Registration Statement on Form S-1 (the “Registration Statement”), of NeuStar, Inc., a Delaware corporation (the “Company”), filed with the Securities and Exchange Commission (the “Commission”) pursuant to Rule 462(b) promulgated under the Securities Act of 1933 (the “Securities Act”), in connection with the public offering of up to 2,575,521 shares (including shares that may be sold upon exercise of the underwriters’ over-allotment option) (the “Shares”) of the Company’s Class A Common Stock, par value $0.001 per share, proposed to be offered by certain stockholders under the Registration Statement (the “Offering”).

     We have examined the originals, or photostatic or certified copies, of such records of the Company and certificates of public officials and such other documents as we have deemed relevant and necessary as the basis for the opinions set forth below. In such examination, we have assumed the genuineness of all signatures, the authenticity of all documents submitted to us as originals, the conformity to original documents of all documents submitted to us as certified or photostatic copies and the authenticity of the originals of such copies. In rendering the opinion set forth below, we have relied as to factual matters upon assurances of certain officers of the Company, which factual matters have not been independently verified by us.

     Based upon the foregoing examination and in reliance thereon, and subject to the assumptions stated and in reliance on statements of fact contained in the documents that we have

NeuStar, Inc.
December 6, 2005
Page 2

examined, we are of the opinion that the Shares to be sold by the selling stockholders have been, or when issued will be, validly issued, fully paid and non-assessable.

     We render no opinion herein as to matters involving the laws of any jurisdiction other than the General Corporation Law of the State of Delaware. We are not admitted to practice in the State of Delaware; however, we are generally familiar with the Delaware General Corporation Law as currently in effect and have made such inquiries as we consider necessary to render this opinion. This opinion is limited to the effect of the current state of the Delaware General Corporation Law and the facts as they currently exist. In rendering this opinion, we assume no obligation to revise or supplement this opinion should current laws, or the interpretations thereof, be changed.

     We consent to the filing of this opinion as an exhibit to the Registration Statement, and we further consent to the use of our name under the caption “Validity of Shares” in the Registration Statement and the prospectus that forms a part thereof. In giving these consents, we do not thereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission.

Very truly yours,

GIBSON, DUNN & CRUTCHER LLP