EXHIBIT 3.1

AMENDED AND RESTATED

CERTIFICATE OF INCORPORATION

OF

AMERIGROUP CORPORATION

FIRST: The name of the corporation (the “Corporation”) is:

AMERIGROUP CORPORATION

SECOND: The address of the Corporation’s registered office in the State of Delaware is c/o The Corporation Trust Company, 1209 Orange Street, Wilmington, Delaware 19801, New Castle County. The name of the Corporation’s registered agent at such address is The Corporation Trust Company.

THIRD: The purpose of the Corporation is to engage, directly or indirectly, in any lawful act or activity for which corporations may be organized under the General Corporation Law of the State of Delaware, as from time to time in effect.

FOURTH: The total number of shares of capital stock that the Corporation has authority to issue is two million twenty thousand (2,020,000) shares of Common Stock, par value $0.01 per share.

FIFTH: To the full extent permitted by the General Corporation Law of the State of Delaware or any other applicable laws presently or hereafter in effect, no director of the Corporation will be personally liable to the Corporation or its stockholders for or with respect to any acts or omissions in the performance of his or her duties as a director of the Corporation. Any repeal or modification of this Article FIFTH will not adversely affect any right or protection of a director of the Corporation existing immediately prior to such repeal or modification.

SIXTH: The Corporation shall indemnify its directors and officers to the fullest extent authorized or permitted by law, as now or hereafter in effect, and such right to indemnification shall continue as to a person who has ceased to be a director or officer of the Corporation and shall inure to the benefit of his or her heirs, executors and personal and legal representatives; provided, however, that except for proceedings to enforce rights to indemnification, the Corporation shall not be obligated to indemnify any director or officer (or his or her heirs, executors or personal or legal representatives) in connection with a proceeding (or part thereof) initiated by such person unless such proceeding (or part thereof) was authorized or consented to by the Board of Directors. The right to indemnification conferred by this Article SIXTH shall include the right to be paid by the Corporation the expenses incurred in defending or otherwise participating in any proceeding in advance of its final disposition.

The Corporation may, to the extent authorized from time to time by the Board of Directors, provide rights to indemnification and to the advancement of expenses to employees and agents of the Corporation similar to those conferred in this Article SIXTH to directors and officers of the Corporation.

The rights to indemnification and to the advance of expenses conferred in this Article SIXTH shall not be exclusive of any other right which any person may have or hereafter acquire under this Certificate of Incorporation, the By-Laws of the Corporation, any statute, agreement, vote of stockholders or disinterested directors or otherwise.

SEVENTH: In furtherance and not in limitation of the rights, powers, privileges, and discretionary authority granted or conferred by the General Corporation Law of the State of Delaware or other statutes or laws of the State of Delaware, the Board of Directors is expressly authorized to make, alter, amend or repeal the By-Laws of the Corporation, without any action on the part of the stockholders, but the stockholders may make additional By-laws and may alter, amend or repeal any By-Law, whether adopted by them or otherwise. The Corporation may in its By-Laws confer powers upon the Board of Directors in addition to the foregoing and in addition to the powers and authorities expressly conferred upon the Board of Directors by applicable law.

EIGHTH: The Corporation reserves the right at any time and from time to time to amend, alter, change or repeal any provision contained in this Certificate of Incorporation, and other provisions authorized by the laws of the State of Delaware at the time in force that may be added or inserted, in the manner now or hereafter prescribed herein or by applicable law; and all rights, preferences and privileges of whatsoever nature conferred upon stockholders, directors or any other persons whomsoever by and pursuant to this Certificate of Incorporation in its present form or as hereafter amended are granted subject to this reservation.

2