Exhibit 3.1

AMENDED AND RESTATED CERTIFICATE OF INCORPORATION

OF

APPTIO, INC.

ARTICLE ONE

The name of the corporation is Apptio, Inc. (the “Corporation”).

ARTICLE TWO

The address of the Corporation’s registered office in the State of Delaware is 251 Little Falls Drive, in the City of Wilmington, County of New Castle, Delaware 19808. The name of its registered agent at such address is Corporation Service Company.

ARTICLE THREE

The nature of the business or purposes to be conducted or promoted 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.

ARTICLE FOUR

The total number of shares of stock which the Corporation has authority to issue is one thousand (1,000) shares of common stock, with a par value of $0.001 per share.

ARTICLE FIVE

The Corporation is to have perpetual existence.

ARTICLE SIX

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 or repeal the by-laws of the Corporation.

ARTICLE SEVEN

Meetings of stockholders may be held within or without the State of Delaware, as the by-laws of the Corporation may provide. The books of the Corporation may be kept outside the State of Delaware at such place or places as may be designated from time to time by the board of directors or in the by-laws of the Corporation. Election of directors need not be by written ballot unless the by-laws of the Corporation so provide.

ARTICLE EIGHT

Subject to any provisions in the by-laws of the Corporation related to indemnification of directors or officers of the Corporation, the Corporation shall indemnify, to the fullest extent permitted by applicable law, any director or officer of the Corporation who was or is a party or is threatened to be made a party to any threatened, pending or completed action, suit or proceeding,

whether civil, criminal, administrative or investigative (a “Proceeding”) by reason of the fact that he or she 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 of another corporation, partnership, joint venture, trust or other enterprise, including service with respect to employee benefit plans, against expenses (including attorneys’ fees), judgments, fines and amounts paid in settlement actually and reasonably incurred by such person in connection with any such Proceeding; provided, however, that the Corporation be required to indemnify a person in connection with a Proceeding (or part thereof) initiated by such person only if such Proceeding (or part thereof) was authorized by the board of directors.

The Corporation shall have the power to indemnify, to the extent permitted by the General Corporation Law of the State of Delaware, as it presently exists or may hereafter be amended from time to time, any employee or agent of the Corporation who was or is a party or is threatened to be made a party to any Proceeding by reason of the fact that he or she 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 of another corporation, partnership, joint venture, trust or other enterprise, including service with respect to employee benefit plans, against expenses (including attorneys’ fees), judgments, fines and amounts paid in settlement actually and reasonably incurred by such person in connection with any such Proceeding.

A right to indemnification or to advancement of expenses arising under a provision of this Amended and Restated Certificate of Incorporation or the by-laws of the Corporation shall not be eliminated or impaired by an amendment to this Amended and Restated Certificate of Incorporation or the by-laws of the Corporation after the occurrence of the act or omission that is the subject of the civil, criminal, administrative or investigative action, suit or proceeding for which indemnification or advancement of expenses is sought, unless the provision in effect at the time of such act or omission explicitly authorizes such elimination or impairment after such action or omission has occurred.

ARTICLE NINE

The Corporation expressly elects not to be governed by Section 203 of the General Corporation Law of the State of Delaware.

ARTICLE TEN

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 herein and by the laws of the State of Delaware, and all rights conferred upon stockholders herein are granted subject to this reservation.