Exhibit 3.1

Amended and Restated

Certificate of Incorporation

1. The name of the corporation is EasyLink Services International Corporation.

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

3. 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 the State of Delaware.

4. The total number of shares of stock that the Corporation shall have authority to issue is one hundred (100), all of which shall be shares of common stock, par value $0.001 per share. All such shares are of one class. The holders of the common stock are entitled to one vote for each share held at all meetings of stockholders (and written actions in lieu of meetings). There shall be no cumulative voting. Election of directors need not be by ballot.

5. The board of directors of the Corporation is authorized to make, alter or repeal the bylaws of the Corporation.

6. No director or officer of the Corporation shall be personally liable to the Corporation for monetary damages for breach of fiduciary duty as a director or officer except for (a) willful misconduct, (b) a crime, unless the director or officer had reasonable cause to believe that the act was lawful, (c) a transaction that resulted in an improper personal benefit of money, property, or service to the director or officer, or (d) an act or omission that is not in good faith and is beyond the scope of authority of the Corporation pursuant to the General Corporation Law of the State of Delaware or this Certificate of Incorporation. If the General Corporation Law of the State of Delaware is hereafter amended to permit a corporation to further eliminate or limit the liability of a director or officer of a corporation, then the liability of a director or officer of the Corporation, in addition to the circumstances in which a director or officer is not personally liable as set forth in the preceding sentence, shall, without further action of the directors, be further eliminated or limited to the fullest extent permitted by the General Corporation Law of the State of Delaware as so amended. Neither any amendment, repeal, or modification of this Section 6, nor the adoption or amendment of any other provision of this Certificate of Incorporation or the bylaws of the Corporation inconsistent with this Section 6 shall adversely affect any right or protection provided hereby with respect to any act or omission occurring prior to the date when such amendment, repeal, modification, or adoption became effective.

7. Each person who was or is a party or is threatened to be made a party to or is involved in any threatened, pending or completed action, suit, proceeding or alternative dispute resolution procedure, whether (i) civil, criminal, administrative, investigative or otherwise, (ii) formal or informal or (iii) by or in the right of the Corporation (collectively, a “proceeding”), by reason of the fact that he or she, or a person of whom he or she is the legal representative, 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, manager, officer, partner, director, employee or agent of another

foreign or domestic corporation or of a foreign or domestic limited liability company, partnership, joint venture, trust or other enterprise, including service with respect to employee benefit plans, whether the basis of such proceeding is alleged action in an official capacity as such a director, officer, employee or agent of the Corporation or in any other capacity while serving as such other director, manager, officer, partner, director, employee or agent, shall be indemnified and held harmless by the Corporation against all judgments, penalties and fines incurred or paid, and against all expenses (including attorneys’ fees) and settlement amounts reasonably incurred or paid, in connection with any such proceeding, except in relation to acts, omissions and transactions described in the first sentence of Section 6 above. Until such time as there has been a final judgment to the contrary, a person shall be presumed to be entitled to be indemnified under this Section 7. The termination of any proceeding by judgment, order, settlement, conviction, or upon a plea of nolo contendere or its equivalent, shall not, of itself, either rebut such presumption or create a presumption that (i) the person is not entitled to indemnification under this Section 7 or (ii) the person was not successful on the merits or otherwise in defense of the proceeding or of any claim, issue or matter therein. If the General Corporation Law of the State of Delaware is hereafter amended to provide for indemnification rights broader than those provided by this Section 7, then the persons referred to in this Section 7 shall be indemnified and held harmless by the Corporation to the fullest extent permitted by the General Corporation Law of the State of Delaware as amended from time to time (but, in the case of any such amendment, only to the extent that such amendment permits the Corporation to provide broader indemnification rights than permitted prior to such amendment).

8. A determination as to whether a person who is a director or officer of the Corporation at the time of the determination is entitled to be indemnified and held harmless under Section 7 shall be made (i) by a majority vote of the directors who are not parties to such proceeding, even though less than a quorum, (ii) by a committee of such directors designated by majority vote of such directors, even though less than a quorum or (iii) if there are no such directors, or if such directors so direct, by independent legal counsel in a written opinion. A determination as to whether a person who is not a director or officer of the Corporation at the time of the determination is entitled to be indemnified and held harmless under Section 7 shall be made by or as directed by the board of directors of the Corporation.

9. The right to indemnification conferred in Section 7 shall include the right to require the Corporation to pay the expenses (including attorneys’ fees) reasonably incurred in defending any such proceeding in advance of its final disposition, provided, however, that, if the board of directors so determines, an advancement of expenses incurred by an indemnitee in his or her capacity as a director or officer of the Corporation (but 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, by or on behalf of such indemnitee, to repay all amounts so advanced if it shall be finally determined that such indemnitee is not entitled to be indemnified for such expenses under Section 7 or otherwise.

10. The right to indemnification and the advancement of expenses conferred in Section 7 shall not be exclusive of any other right which any person may have or hereafter acquire under any statute, any provision of this Certificate of Incorporation or of any bylaw, any agreement, insurance policy or arrangement, any vote of disinterested directors, or otherwise. The board of directors is expressly authorized to adopt and enter into indemnification agreements with, and obtain insurance for, directors and officers.

11. Neither any amendment, repeal, or modification of the foregoing Sections 7 through 10, nor the adoption or amendment of any other provision of this Certificate of Incorporation or the bylaws of the Corporation inconsistent with anything set forth in Sections 7-11, shall adversely affect any right or protection provided hereby with respect to any act or omission occurring prior to the date when such amendment, repeal, modification, or adoption became effective. Notwithstanding anything in the foregoing to the contrary, the provisions of the foregoing Sections 7-11 shall not be applicable to any person who served as a director of any corporation which is merged into the Corporation on or before April 26, 2012.

12. In the event any provision (or portion thereof) of this Certificate of Incorporation shall be found to be invalid, prohibited, or unenforceable for any reason, the remaining provisions (or portions thereof) of this Certificate of Incorporation shall be deemed to remain in full force and effect, and shall be construed as if such invalid, prohibited, or unenforceable provision had been stricken herefrom or otherwise rendered inapplicable, it being the intent of the Corporation that each such remaining provision (or portion thereof) of this Certificate of Incorporation remain, to the fullest extent permitted by law, applicable and enforceable, notwithstanding any such finding.

13. 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 this Certificate of Incorporation, and all rights conferred upon stockholders herein are granted subject to this reservation.