EXHIBIT 3.1

AMENDED AND RESTATED

CERTIFICATE OF INCORPORATION

OF

CBEYOND, INC.

FIRST: The name of the corporation is Cbeyond, Inc. (the “Corporation”).

SECOND: The address of its registered office in the State of Delaware is Corporation Service Company, 2711 Centerville Road, Suite 400, Wilmington, New Castle County, Delaware, 19808. The name of its registered agent at such address is Corporation Service Company.

THIRD: The purpose of the Corporation is to engage in any lawful act or activity for which corporations may be organized under the General Corporation Law of Delaware, as it may be amended from time to time, or any successor law.

FOURTH. The total number of shares of stock which the Corporation shall have authority to issue is one thousand (1,000). All such shares are to be common stock, par value of $.01 per share, and are to be of one class.

FIFTH: The Board of Directors is authorized to adopt, amend or repeal the bylaws of the Corporation, except as otherwise provided therein. Election of directors need not be by ballot.

SIXTH: No director of the Corporation shall be liable to the Corporation or its stockholders for monetary damages for breach of fiduciary duty as a director, except for liability (a) for any breach of the director’s duty of loyalty to the Corporation or its stockholders, (b) for acts or omissions not in good faith or which involve intentional misconduct or a knowing violation of law, (c) under Section 174 of the Delaware General Corporation Law, or (d) for any transaction from which the director derived an improper personal benefit. If the Delaware General Corporation Law hereafter is amended to authorize the further elimination or limitation of the liability of directors, then the liability of a director of the Corporation, in addition to the limitation on personal liability provided herein, shall be eliminated or limited to the fullest extent permitted by the amended Delaware General Corporation Law. The Corporation shall have power, to the fullest extent permitted by Section 145 of the Delaware General Corporation Law, as the same may be amended or supplemented, to indemnify any person who was or is a party or is threatened to be made a party to an action, suit, or proceeding, whether civil, criminal, administrative, or investigative, by reason of the fact that the person is or was a director or officer of the Corporation, or is or was serving at the request of the Corporation as a director, officer, employee or agent of another corporation, partnership, joint venture, trust or other enterprise from and against any and all of the expenses, liabilities or other matters referred to in or covered by said section, and the indemnification provided for herein shall not be deemed exclusive of any other rights to which those indemnified may be entitled under any bylaw, agreement, vote of stockholders or disinterested directors or otherwise, both as to action in his or her official capacity and as to action in another capacity while holding such office, and shall continue as to a person who has ceased to be a director, officer, employee or agent and shall inure to the benefit of the heirs, executors and administrators of such person. Indemnification conferred pursuant to 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 upon receipt by the Corporation of an undertaking by or on behalf of the person receiving advancement to repay the amount advanced if it shall ultimately be determined that such person is not entitled to be indemnified by the Corporation under this Article SIXTH. Any repeal or modification of this section by the stockholders of the Corporation shall be prospective only and shall not adversely affect any limitation on the personal liability of a director of the Corporation existing at the time of such repeal or modification.

SEVENTH: The Corporation reserves the right to amend, alter, change or repeal any provision contained in this 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.