Exhibit 3.21

AMENDED AND RESTATED

CERTIFICATE OF INCORPORATION

OF

NEWPAGE HOLDINGS INC.

ARTICLE I

NAME

The name of the Corporation is NewPage Holdings Inc.

ARTICLE II

REGISTERED OFFICE

The address of the Corporation’s registered office in the State of Delaware is 615 South DuPont Highway, Dover, County of Kent, 19901, and the name of its registered agent at such address is National Corporate Research, Ltd.

ARTICLE III

CORPORATE PURPOSE

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 (as amended or modified from time to time, the “DGCL”).

ARTICLE IV

AUTHORIZED CAPITAL STOCK

The total number of shares of all classes of capital stock that the Corporation shall have the authority to issue is 1,000 shares, all of which shall be common stock, par value $0.01 per share.

ARTICLE V

LIMITATION OF DIRECTOR LIABILITY

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 to the extent such exculpation is not permitted under the DGCL. If the DGCL is hereafter amended to authorize corporate action further eliminating or limiting the personal liability of directors, then the liability of the directors of the Corporation shall be eliminated or limited to the fullest extent permitted under the DGCL, as so amended. Any amendment, modification or repeal of this Article shall not adversely affect any right or protection of a director of the Corporation existing at the time of, or increase the liability of any director of the Corporation with respect to any acts or omissions of such director occurring prior to, such amendment, modification or repeal.

ARTICLE VI

INDEMNIFICATION OF DIRECTORS AND OFFICERS

Section 1. General. To the fullest extent permitted by applicable law as it presently exists or may hereafter be amended, and as may be set forth more fully in the Bylaws of the Corporation, the Corporation shall indemnify and hold harmless, and shall advance expenses to, any person who was or is made or is threatened to be made a party or is otherwise involved in any action, suit or proceeding, whether civil, criminal, administrative or investigative, by reason of the fact that he or she, or a person for whom he or she is the legal representative, is or was a director or officer of the Corporation or, while a director or officer of the Corporation, is or was serving at the request of the Corporation as a director, officer, employee or agent of another corporation or of a partnership, joint venture, trust, enterprise or nonprofit entity, including service with respect to employee benefit plans maintained or sponsored by the Corporation, against all liability and loss suffered and expenses (including attorneys’ fees) reasonably incurred by such person, and such right to indemnification shall continue as to any 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. For the avoidance of doubt, nothing contained in this Article or otherwise contained in this Certificate of Incorporation or in the Bylaws of the Corporation shall require the Corporation to indemnify or hold harmless any person with respect to any act, omission or event that occurred prior to the date the Corporation was formed.

Section 2. Rights not Exclusive. The rights to indemnification and to the advancement of expenses conferred in this Article shall not be exclusive of any other right which any person may have or hereafter acquire under this Certificate of Incorporation, the Bylaws of the Corporation, any statute, agreement, vote of stockholders or disinterested directors or otherwise.

Section 3. Amendments to this Article. Any repeal or modification of this Article shall not adversely affect any rights to indemnification and to the advancement of expenses of a director or officer of the Corporation existing at the time of such repeal or modification with respect to any acts or omissions occurring prior to such repeal or modification.

ARTICLE VII

SECTION 203 OF DGCL

The Corporation elects not to be governed by Section 203 of the DGCL.

ARTICLE VIII

EXCLUSIVE FORUM

Unless the Corporation consents in writing to the selection of an alternative forum, the sole and exclusive forum for (a) any derivative action or proceeding brought on behalf of the Corporation, (b) any action asserting a claim of breach of a fiduciary

2

duty owed by any director, officer, employee or agent of the Corporation to the Corporation or the Corporation’s stockholders, (c) any action asserting a claim arising pursuant to any provision of the DGCL, this Certificate of Incorporation, or the Bylaws of the Corporation (as either may be amended or modified from time to time), or (d) any action asserting a claim governed by the internal affairs doctrine shall be a state court located within the State of Delaware or, if no state court located within the State of Delaware has jurisdiction, the federal district court for the District of Delaware, in all cases subject to the court having personal jurisdiction over the indispensable parties named as defendants therein. Any person or entity purchasing or otherwise acquiring any interest in shares of capital stock of the Corporation shall be deemed to have notice of and consent to the provisions of this Article.

* * * * *

3