EXHIBIT 5.1

September 16, 2005

Direct Dial
(202) 955-8500 Client Matter Number
C 66460-00021

Fax No.
(202) 467-0539

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

Re: NeuStar, Inc. – 1999 Equity Incentive Plan and 2005 Stock Incentive Plan Registration Statement on Form S-8

Ladies and Gentlemen:

     We have examined the Registration Statement on Form S 8 (the “Registration Statement”), of NeuStar, 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 “Securities Act”), in connection with the offering by the Company of up to 20,579,473 shares of the Company’s Class A Common Stock, par value $0.001 per share (the “Shares”). The Shares subject to the Registration Statement are to be issued under the NeuStar, Inc. 1999 Equity Incentive Plan and the NeuStar, Inc. 2005 Stock Incentive Plan (the “Plans”).

     We have examined the originals, or photostatic or certified copies, of such records of the Company and certificates of officers of the Company and of public officials and such other documents as we have deemed relevant and necessary as the basis for the opinions set forth below. In our examination, we have assumed the genuineness of all signatures, the legal capacity and competency of all natural persons, the authenticity of all documents submitted to us as originals and the conformity to original documents of all documents submitted to us as copies. We have also assumed that there are no agreements or understandings between or among the Company and any participants in the Plans that would expand, modify or otherwise affect the terms of the Plans or the respective rights or obligations of the participants thereunder.

E-1

NeuStar, Inc.
September 16, 2005
Page 2

     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 examined, we are of the opinion that the Shares, when issued in accordance with the terms set forth in the respective Plan and against payment therefor, 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 “Legal Matters” 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,

/s/ Gibson, Dunn & Crutcher LLP

Gibson, Dunn & Crutcher LLP

E-2