Exhibit 3.1

FIFTH AMENDED AND RESTATED

CERTIFICATE OF INCORPORATION

OF

NEUSTAR, INC.

I.    Name. The name of the corporation is NeuStar, Inc. (the “Corporation”).

II.    Registered Office. The address of the Corporation’s registered office in the State of Delaware is 1209 Orange Street, Wilmington, DE 19801, County of New Castle. The name of its registered agent at such address is The Corporation Trust Company.

III.    Purpose. The purpose of the Corporation is to engage in any lawful act or activity for which corporations may be organized under the Delaware General Corporation Law, as the same exists or as may hereafter be amended from time to time.

IV.    Authorized Stock. This Corporation is authorized to issue one class of shares to be designated Common Stock. The total number of shares of Common Stock the Corporation has authority to issue is 1,000 with par value of $0.001 per share.

V.    Bylaws. In furtherance and not in limitation of the powers conferred by statute, the board of directors of the Corporation is expressly authorized to make, alter, amend or repeal the bylaws of the Corporation.

VI.    Election of Directors. Elections of directors need not be by written ballot unless otherwise provided in the bylaws of the Corporation.

VII.    Indemnification

A.    Right to Indemnification.

1.    Subject to the limitations set forth in Section A.2 of this Article VII, each person who was or is made a party or is threatened to be made a party to or is otherwise involved in any Proceeding, by reason of the fact that he or she is or was a director or an executive officer of the Corporation or is or was a director or executive officer of the Corporation serving at the request of the Corporation as a director, officer, trustee or agent of another corporation or of a partnership, joint venture, trust or other enterprise, including service with respect to an employee benefit plan (such person, an “Indemnitee”), whether the basis of such Proceeding is alleged action in an official capacity as a director, officer, trustee or agent or in any other capacity while serving as a director, officer, trustee or agent, shall be indemnified and held harmless by the Corporation to the fullest extent authorized by the Delaware General Corporation Law, as the same exists or may hereafter be amended (but, in the case of any such amendment, only to the extent that such amendment permits the Corporation to provide broader indemnification rights than such law permitted the Corporation to provide prior to such amendment), against all

1

expense, liability and loss (including attorneys’ fees, judgments, fines, ERISA excise taxes or penalties and amounts paid in settlement) reasonably incurred or suffered by such Indemnitee in connection therewith.

2.    Notwithstanding any other provision in this Article VII, the Corporation shall not be obligated under this Article VII to make any indemnity in connection with any claim made against an Indemnitee: (a) to the extent expressly prohibited by applicable law; (b) for which payment has actually been made to Indemnitee under a valid and collectible insurance policy or under a valid and enforceable indemnity clause, bylaw or agreement of the Corporation or any other company or organization on whose board Indemnitee serves at the request of the Corporation, except with respect to any deductible (or the equivalent) from or excess beyond the amount payable or paid under any insurance policy or other indemnity provision; (c) for an accounting of profits made (i) from the purchase and sale (or sale and purchase) by the Indemnitee of securities of the Corporation within the meaning of Section 16(b) of the Securities Exchange Act of 1934, as amended, or similar provisions of state statutory law or common law, or (ii) from any transactions prohibited under Section 306(a) of the Sarbanes-Oxley Act of 2002; or (d) in connection with any Proceeding (or any part of any Proceeding), including claims and counterclaims, initiated or brought voluntarily by the Indemnitee, including any Proceeding (or any part of any Proceeding) initiated by such Indemnitee against the Corporation or its directors, officers, employees or other Indemnitees in their capacity as such, unless (i) the Proceeding is brought pursuant to Section C of this Article VII with respect to the enforcement of rights to indemnification under this Article, (ii) the Board of Directors authorized the Proceeding (or such part of any Proceeding) prior to its initiation or (iii) the Corporation elects to provide the indemnification, in its sole discretion, pursuant to the powers vested in the Corporation under applicable law.

B.    Right to Advancement of Expenses.    In addition to the right to indemnification conferred in Section A of this Article VII, an Indemnitee shall also have the right to be paid by the Corporation the expenses (including attorney’s fees) incurred in defending any such Proceeding in advance of its final disposition (hereinafter an “advancement of expenses”); provided, however, that, if the Delaware General Corporation Law requires, an advancement of expenses incurred by an Indemnitee in his or her capacity as a director or officer (and not in any other capacity in which service was or is rendered by such Indemnitee, including, without limitation, service to an employee benefit plan) shall be made only upon delivery to the Corporation of an undertaking (hereinafter an “undertaking”), by or on behalf of such Indemnitee, to repay all amounts so advanced if it shall ultimately be determined by final judicial decision from which there is no further right to appeal (hereinafter a “final adjudication”) that such Indemnitee is not entitled to be indemnified for such expenses under this Section B or otherwise. Notwithstanding the foregoing, the Corporation shall not be required to advance any expenses to an Indemnitee in the event and to the extent that such Indemnitee has entered a plea of guilty in the applicable criminal Proceeding.

C.    Right of Indemnitee to Bring Suit.    If a claim under Section A or B of this Article VII is not paid in full by the Corporation within 60 days after a written claim has been received by the Corporation, except in the case of a claim for an advancement of expenses, in which case

2

the applicable period shall be 20 days, the Indemnitee may at any time thereafter bring suit against the Corporation to recover the unpaid amount of the claim. If successful in whole or in part in any such suit, or in a suit brought by the Corporation to recover an advancement of expenses pursuant to the terms of an undertaking, the Indemnitee shall be entitled to be paid also the expense of prosecuting or defending such suit. In (a) any suit brought by the Indemnitee to enforce a right to indemnification hereunder (but not in a suit brought by the Indemnitee to enforce a right to an advancement of expenses) it shall be a defense that the Indemnitee has not met any applicable standard for indemnification set forth in the Delaware General Corporation Law, and (b) in any suit brought by the Corporation to recover an advancement of expenses pursuant to the terms of an undertaking, the Corporation shall be entitled to recover such expenses upon a final adjudication that the Indemnitee has not met any applicable standard for indemnification set forth in the Delaware General Corporation Law. Neither the failure of the Corporation (including its directors who are not parties to such action, a committee of such directors, independent legal counsel, or its stockholders) to have made a determination prior to the commencement of such suit that indemnification of the Indemnitee is proper in the circumstances because the Indemnitee has met the applicable standard of conduct set forth in the Delaware General Corporation Law, nor an actual determination by the Corporation (including its directors who are not parties to such action, a committee of such directors, independent legal counsel, or its stockholders) that the Indemnitee has not met such applicable standard of conduct, shall create a presumption that the Indemnitee has not met the applicable standard of conduct or, in the case of such a suit brought by the Indemnitee, be a defense to such suit. In any suit brought by the Indemnitee to enforce a right to indemnification or to an advancement of expenses hereunder, or brought by the Corporation to recover an advancement of expenses pursuant to the terms of an undertaking, the burden of proving that the Indemnitee is not entitled to be indemnified, or to such advancement of expenses, under this Article VII or otherwise shall be on the Corporation.

D.    Non-Exclusivity of Rights.    The rights to indemnification and to the advancement of expenses conferred in this Article VII shall not be exclusive of any other right which any person may have or hereafter acquire under any statute, the Corporation’s Certificate of Incorporation, Bylaws, agreement, vote of stockholders or directors or otherwise.

E.    Insurance.    The Corporation may maintain insurance, at its expense, to protect itself and/or any director, officer, employee or agent of the Corporation or another corporation, partnership, joint venture, trust or other enterprise against any expense, liability or loss, whether or not the Corporation would have the power to indemnify such person against such expense, liability or loss under the Delaware General Corporation Law.

F.    Indemnification of Employees and Agents of the Corporation.    The Corporation may, to the extent authorized from time to time by the Board of Directors, grant rights to indemnification and to the advancement of expenses to any employee or agent of the Corporation (or any of its direct or indirect subsidiaries or affiliates) who does not qualify for indemnification as an Indemnitee under this Article VII to the fullest extent of the provisions of this Article with respect to the indemnification and advancement of expenses of directors and executive officers of the Corporation.

3

G.    Nature of Rights.    The rights conferred upon Indemnitees in this Article VII shall be contract rights and such rights shall continue as to an Indemnitee who has ceased to be a director, officer or trustee and shall inure to the benefit of the Indemnitee’s heirs, executors and administrators. Any amendment, alteration or repeal of this Article VII that adversely affects any right of an Indemnitee or its successors shall be prospective only and shall not limit or eliminate any such right with respect to any Proceeding involving any occurrence or alleged occurrence of any action or omission to act that took place prior to such amendment or repeal.

H.    Certain Definitions.    For purposes of this Article VII, the following terms shall be defined as follows:

1.    “executive officer” shall mean (a) any officer of the Corporation with a position of senior vice president (or, if applicable, executive vice president) or higher; or (b) any other officer of the Corporation who is expressly designated by a resolution of the Board of Directors as an “executive officer” for purposes of this Article (regardless of whether such person is designated as an executive officer for other purposes). If an individual is designated an “executive officer” by virtue of clause (a) or (b) of this Section H.1, and the Board of Directors subsequently ceases to designate such individual as an “executive officer,” such individual shall continue to be treated as an “executive officer” with respect to any Proceeding involving any occurrence or alleged occurrence of any action or omission to act that took place a period when such individual was an “executive officer” pursuant to clause (a) or (b) of this Section H.1.

2.    “Proceeding” includes any threatened, pending or completed action, suit, arbitration, alternate dispute resolution mechanism, investigation, inquiry, administrative or legislative hearing or any other actual, threatened or completed proceeding, including any and all appeals, whether brought in the right of the Corporation or otherwise and whether of a civil, criminal, administrative or investigative nature, in which Indemnitee was involved, or becomes or may become involved, as a party or otherwise, for which indemnification is not prohibited under Section A.2 of this Article VII, including, but not limited to, actions, suits or proceedings in which Indemnitee may be or may have been involved as a party or otherwise, by reason of the fact that Indemnitee is or was a director, officer, employee or agent of the Corporation, or is or was serving, at the request of the Corporation, as a director, officer, employee or agent or fiduciary of any other entity, including, but not limited to, another corporation, partnership, joint venture, trust, employee benefit plan or other enterprise, or by reason of anything done or not done by Indemnitee in any such capacity, whether or not Indemnitee is serving in such capacity at the time any liability or expense is incurred for which indemnification, reimbursement or advancement of expenses can be provided under this Article VII.

I.    Constituent Corporations.    For the purposes of this Article VII, references to the “Corporation” include all constituent corporations absorbed in a consolidation or merger as well as the resulting or surviving corporation, so that any person who is or was a director or officer, employee or agent of such a constituent corporation or is or was serving at the request of such constituent corporation as a director, officer, employee or agent of another corporation, partnership, joint venture, trust or other enterprise shall stand in the same position under the provisions of this Article VII with respect to the resulting or surviving corporation as he would if he had served the resulting or surviving corporation in the same capacity.

4

VIII.    Amendment. Except as provided in Article VII above, the Corporation reserves the right to amend, alter, change or repeal any provision contained in this Fourth Amended and Restated Certificate of Incorporation, in the manner now or hereafter prescribed by statute, and all rights conferred upon stockholders herein are granted subject to this reservation.

IX.    Corporate Opportunities.

A. In recognition of the fact that the Corporation, on the one hand, and the Investor Group (as defined below), on the other hand, may currently engage in, and may in the future engage in, the same or similar activities or lines of business and have an interest in the same areas and types of corporate opportunities, and in recognition of the benefits to be derived by the Corporation, through its continued contractual, corporate and business relations with the Investor Group (including possible service of directors, officers and employees of the Investor Group as directors, officers and employees of the Corporation), the provisions of this Article IX are set forth to regulate and define the conduct of certain affairs of the Corporation, as they may involve the Investor Group, and the powers, rights, duties and liabilities of the Corporation, as well as its directors, officers, employees and stockholders in connection therewith. To the fullest extent permitted by law and except as otherwise agreed in writing: (i) each member of the Investor Group shall have the right to, and shall have no duty (contractual or otherwise) not to, directly or indirectly, (A) engage in the same, similar or competing business activities or lines of business as the Corporation, (B) do business with any client or customer of the Corporation or (C) make investments in competing businesses of the Corporation, and such acts shall not be deemed wrongful or improper; (ii) no member of the Investor Group shall be liable to the Corporation for breach of any duty (contractual or otherwise), including without limitation fiduciary duties, by reason of any such activities or of such person’s or entity’s participation therein; and (iii) in the event that any member of the Investor Group acquires knowledge of a potential transaction or matter that may be a corporate opportunity for the Corporation, on the one hand, and any member of the Investor Group, on the other hand, or any other person or entity, no member of the Investor Group shall have any duty (contractual or otherwise), including without limitation fiduciary duties, to communicate, present or offer such corporate opportunity to the Corporation and shall not be liable to the Corporation for breach of any duty (contractual or otherwise), including without limitation fiduciary duties, by reason of the fact that any member of the Investor Group directly or indirectly pursues or acquires such opportunity for itself, directs such opportunity to another person or entity, or does not present or communicate such opportunity to the Corporation, even though such corporate opportunity may be of a character that, if presented to the Corporation, could be taken by the Corporation. The Corporation hereby renounces any interest, right, or expectancy in any such opportunity not offered to it by the Investor Group to the fullest extent permitted by law.

B. For purposes of this Article IX, the “Investor Group” means Golden Gate Private Equity, Inc., Hux Investment Pte. Ltd. and their respective affiliates and any of their respective managed investment funds and portfolio companies (other than the Corporation and its subsidiaries) and their respective partners, members, directors, employees, stockholders, agents, any successor by operation of law (including by merger) of any such person, and any entity that acquires all or substantially all of the assets of any such person in a single transaction or series of related transactions.

5

C. Neither the alteration, amendment or repeal of this Article IX nor the adoption of any provision of this Certificate of Incorporation inconsistent with this Article IX shall eliminate or reduce the effect of this Article IX in respect of any matter occurring, or any cause of action, suit or claim that, but for this Article IX, would accrue or arise, prior to such alteration, amendment, repeal or adoption.

6