Exhibit 4.1

EXECUTION VERSION

SHAREHOLDERS’ AGREEMENT

OF

CELLU TISSUE HOLDINGS, INC.

Dated as of January 27, 2010

Table of Contents

i

SHAREHOLDERS’ AGREEMENT

of

CELLU TISSUE HOLDINGS, INC.

This SHAREHOLDERS’ AGREEMENT (as the same may be amended, modified or supplemented from time to time, the “Agreement”), is made and entered into as of this 27^th day of January, 2010, by and between Cellu Tissue Holdings, Inc., a Delaware corporation (the “Company”) and Weston Presidio V, L.P., a Delaware limited partnership (“Weston”).

RECITALS:

WHEREAS, the Company filed a registration statement on Form S-1 (File No. 333-162543) and certain amendments thereto with the U.S. Securities and Exchange Commission relating to the proposed initial public offering (the “IPO”) of the Company’s common stock, par value $0.01 per share (the “Common Stock”);

WHEREAS, on and following the date of completion of the IPO (the “Closing Date”), Weston and the Company wish to provide for certain corporate governance matters in accordance with the terms of this Agreement; and

WHEREAS, effective immediately prior to the closing of the IPO, Weston and the Company, as successor in interest to Cellu Parent Corporation, a Delaware corporation (“Cellu Parent”), desire to terminate the Shareholders Agreement dated as of June 12, 2006, by and among Weston, Cellu Parent and certain other shareholders set forth therein (the “Prior Shareholders Agreement”).

NOW, THEREFORE, in consideration of the mutual covenants contained herein and other good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, the parties to this Agreement hereby agree as follows:

ARTICLE I

DEFINITIONS

SECTION 1.1. Definitions. Capitalized terms used herein have the following meanings:

“2010 Annual Meeting” means the annual meeting of the Company’s shareholders to be held in 2010.

“2013 Annual Meeting” means the annual meeting of the Company’s shareholders to be held in 2013.

“Action” has the meaning set forth in Section 3.7.

“Affiliate” means, with respect to any Person, an “affiliate” as defined in Rule 405 of the regulations promulgated under the Securities Act.

“Agreement” has the meaning set forth in the Preamble.

“beneficially own” or “beneficial ownership” has the meaning ascribed to such terms in Rule 13d-3 under the Exchange Act.

“Board” shall mean the board of directors of the Company.

“Cellu Parent” has the meaning set forth in the Recitals.

“Certificate of Incorporation” means the Company’s Amended and Restated Certificate of Incorporation as in effect immediately following the Closing Date.

“Change of Control” means: (i) the sale of all or substantially all of the assets of the Company to any Person (or group of Persons acting in concert), other than to any employee benefit plan (or trust forming a part thereof) maintained by the Company or its Affiliates or other Person of which a majority of its voting power or other equity securities is owned, directly or indirectly, by the Company; or (ii) a merger, recapitalization or other sale by the Company or any of its Affiliates, to a Person (or group of Persons acting in concert) of shares of Common Stock or other equity interests of the Company that results in more than 50% of the shares of Common Stock or other equity interests of the Company (or any resulting company after a merger) being held by a Person (or group of Persons acting in concert) other than (x) the shareholders of the Company immediately prior to such transaction or (y) an employee benefit plan (or trust forming a part thereof) maintained by the Company or its Affiliates or other Person of which a majority of its voting power or other equity securities is owned, directly or indirectly, by the Company.

“Closing Date” has the meaning set forth in the Recitals.

“Common Stock” has the meaning set forth in the Recitals.

“Company” has the meaning set forth in the Preamble.

“Director” means a member of the Company’s Board.

“Exchange Act” shall mean the Securities Exchange Act of 1934, as amended from time to time, and the rules and regulations promulgated pursuant thereto.

“Governmental Authority” means any: (i) nation, state, commonwealth, province, territory, county, municipality, district or other jurisdiction of any nature; (ii) U.S. and other federal, state, local, municipal, foreign or other government; or (iii) governmental or quasi-governmental authority of any nature (including any governmental division, department, agency, commission, instrumentality, official, organization, unit, body or entity and any court or other tribunal).

“IPO” has the meaning set forth in the Recitals.

2

“Law” means any applicable constitutional provision, statute, act, code, law, regulation, rule, ordinance, order, decree, ruling, proclamation, resolution, judgment, decision, declaration, or interpretative or advisory opinion or letter of a Governmental Authority and shall include, for the avoidance of any doubt, the General Corporation Law of the State of Delaware and the listing or other standards of any applicable stock exchange.

“Person” means any natural person, corporation, limited partnership, general partnership, limited liability company, joint stock company, joint venture, association, company, estate, trust, bank trust company, land trust, business trust, or other organization, whether or not a legal entity, custodian, trustee-executor, administrator, nominee or entity in a representative capacity and any government or agency or political subdivision thereof.

“Prior Shareholders Agreement” has the meaning set forth in the Recitals.

“Registration Rights Agreement” means the Registration Rights Agreement, dated as of June 12, 2006, by and among Cellu Parent, Weston and certain other shareholders set forth therein.

“Securities Act” means the Securities Act of 1933, as amended from time to time, and the rules and regulations promulgated pursuant thereto.

“Weston” has the meaning set forth in the Preamble.

“Weston Designee” has the meaning set forth in Section 2.1(a).

SECTION 1.2. Construction. Whenever the context requires, the gender of all words used in this Agreement includes the masculine, feminine and neuter forms and the singular form of words shall include the plural and vice versa. All references to Sections refer to sections of this Agreement. Whenever the words “include,” “includes” or “including” are used in this Agreement, they shall be deemed to be followed by the words “without limitation” (except to the extent the context otherwise provides). This Agreement shall be construed without regard to any presumption or rule requiring construction or interpretation against the party drafting or causing any instrument to be drafted.

ARTICLE II

CORPORATE GOVERNANCE SECTION

SECTION 2.1. Board of Directors.

(a) Following the Closing Date, Weston shall have the right, but not the obligation, to nominate at the 2010 Annual Meeting, one designee for election to the Board. Such designee whom Weston nominates pursuant to this Section 2.1(a) and is thereafter elected to the Board is referred to herein as the “Weston Designee”. The Weston Designee shall be a Class I director pursuant to the Certificate of Incorporation.

(b) Subject to the Board’s fiduciary duties to the Company’s shareholders under applicable Law, in the event that a vacancy is created at any time by the death, disability,

3

retirement or resignation of the Weston Designee prior to the 2013 Annual Meeting, the remaining Directors and the Company shall cause the vacancy created thereby to be filled by a new designee of Weston, and the Company hereby agrees to take, prior to the 2013 Annual Meeting, all actions necessary to accomplish the same. A Director elected to fill such a vacancy shall be elected for the unexpired term of his or her predecessor in office.

(c) Subject to the Board’s fiduciary duties to the Company’s shareholders under applicable Law, the Company agrees at the 2010 Annual Meeting to include in the slate of nominees recommended by the Board, the individual designated by Weston pursuant to this Section 2.1 and to use its best efforts to cause the election of such individual to the Board, including nominating such individual to be elected as a Director as provided herein.

SECTION 2.2. Consent Rights. Following the Closing Date, for so long as Weston beneficially owns 35% or more of the then outstanding shares of Common Stock, the following actions by the Company or any of its subsidiaries shall require the approval of Weston, in addition to the Board’s approval (or the approval of the requisite governing body of any subsidiary of the Company):

(a) the hiring or firing of the chief executive officer of the Company;

(b) any Change of Control;

(c) entering into any agreement providing for the acquisition or divestiture of assets or Persons, in each such case providing for aggregate consideration in excess of $50 million; and

(d) any issuance of equity securities by the Company or any of its subsidiaries for aggregate consideration in excess of $25 million.

SECTION 2.3. Termination of Prior Shareholders Agreement.

(a) The Prior Shareholders Agreement is hereby terminated in its entirety, effective immediately prior to the closing of the IPO. Weston and the Company agree that neither Weston, the Company, the Other Shareholders (as defined in the Prior Shareholders Agreement), nor any of their respective Affiliates, successors or assigns, shall have any further rights or obligations under the Prior Shareholders Agreement or any continuing liability to any party thereto.

(b) Each of Weston and the Company hereby waive any rights it may have under the Prior Shareholders Agreement that conflict with or otherwise prohibit the termination contemplated hereby, including without limitation any notice requirements required under the Prior Shareholders Agreement.

4

ARTICLE III

GENERAL PROVISIONS

SECTION 3.1. Notices.

(a) Except as expressly set forth to the contrary in this Agreement, all notices, requests or consents provided for or required to be given hereunder shall be in writing and shall be deemed to be duly given if personally delivered, telecopied and confirmed, or mailed by certified mail, return receipt requested, or nationally recognized overnight delivery service with proof of receipt maintained, at the following addresses (or any other address that any such party may designate by written notice to the other party):

c/o Weston Presidio V, L.P.

Pier 1, Bay 2

San Francisco, CA 94111

Attention: R. Sean Honey and Therese Mrozek

Fax: (415) 398-0990

with a copy (which shall not constitute notice) to:

Kirkland & Ellis LLP

300 North LaSalle

Chicago, Illinois 60654

Attention: Robert M. Hayward

Fax: (312) 862-2200

Cellu Tissue Holdings, Inc.

1855 Lockeway Drive, Suite 501

Alpharetta, Georgia 30004

Attention: General Counsel

Fax: (678) 393-2657

with a copy (which shall not constitute notice) to:

King & Spalding LLP

1180 Peachtree Street, N.E.

Atlanta, GA 30309

Attention: Alan J. Prince

Fax: (404) 572-5133

(b) Any such notice shall, if delivered personally, be deemed received upon delivery; shall, if delivered by telecopy, be deemed received on the first business day following confirmation; shall, if delivered by nationally recognized overnight delivery service, be deemed received the first business day after being sent; and shall, if delivered by mail, be deemed received upon the earlier of actual receipt thereof or five (5) business days after the date of deposit in the United States mail.

5

(c) Whenever any notice is required to be given by Law or this Agreement, a written waiver thereof, signed by the Person entitled to notice, whether before or after the time stated therein, shall be deemed equivalent to the giving of such notice.

SECTION 3.2. Amendment; Waiver. This Agreement may be amended, supplemented or otherwise modified only by a written instrument executed by each of the parties hereto. No waiver by any party of any of the provisions hereof will be effective unless explicitly set forth in writing and executed by the party so waiving. The waiver by any party hereto of a breach of any provision of this Agreement will not operate or be construed as a waiver of any subsequent breach.

SECTION 3.3. Further Assurances. The parties hereto will sign such further documents, cause such meetings to be held, resolutions passed, exercise their votes and do and perform and cause to be done such further acts and things necessary, proper or advisable in order to give full effect to this Agreement and every provision hereof.

SECTION 3.4. Assignment. This Agreement will inure to the benefit of and be binding on the parties hereto and their respective successors and permitted assigns. Except as specifically provided herein, this Agreement may not be assigned without the express prior written consent of the other party hereto, and any attempted assignment, without such consents, will be null and void.

SECTION 3.5. Third Parties. This Agreement does not create any rights, claims or benefits inuring to any person that is not a party hereto nor create or establish any third party beneficiary hereto.

SECTION 3.6. Governing Law. This Agreement shall be governed by and construed in accordance with the laws of the State of Delaware, without regard to its conflict of laws principles.

SECTION 3.7. Jurisdiction. Each party to this Agreement, by its execution hereof, (a) hereby irrevocably submits to the exclusive jurisdiction of the state courts of the State of Delaware or the United States District Court located in the State of Delaware for the purpose of any action, claim, cause of action or suit (in contract, tort or otherwise) (“Action”) between the parties arising in whole or in part under or in connection with this Agreement, (b) hereby waives to the extent not prohibited by applicable law, and agrees not to assert, by way of motion, as a defense or otherwise, in any such Action, any claim that it is not subject personally to the jurisdiction of the above-named courts, that its property is exempt or immune from attachment or execution, that any such Action brought in one of the above-named courts should be dismissed on grounds of forum non conveniens, should be transferred or removed to any court other than one of the above-named courts, or should be stayed by reason of the pendency of some other proceeding in any other court other than one of the above-named courts, or that this Agreement or the subject matter hereof may not be enforced in or by such court and (c) hereby agrees not to commence any such Action other than before one of the above-named courts. Notwithstanding the previous sentence, a party may commence any Action in a court other than the above-named courts solely for the purpose of enforcing an order or judgment issued by one of the above-named courts. EACH OF THE PARTIES HERETO HEREBY WAIVES TRIAL BY JURY IN ANY JUDICIAL PROCEEDING INVOLVING ANY DISPUTE, CONTROVERSY OR CLAIM ARISING OUT OF OR RELATING TO THIS AGREEMENT.

6

SECTION 3.8. Specific Performance. Each party hereto acknowledges and agrees that in the event of any breach of this Agreement by any of them, the other party hereto would be irreparably harmed and could not be made whole by monetary damages. Each party accordingly agrees to waive the defense in any action for specific performance that a remedy at law would be adequate and that the parties, in addition to any other remedy to which they may be entitled at law or in equity, shall be entitled to specific performance of this Agreement without the posting of bond.

SECTION 3.9. Entire Agreement. This Agreement sets forth the entire understanding of the parties hereto with respect to the subject matter hereof. Except as set forth in the Certificate of Incorporation or in the Registration Rights Agreement (a) there are no agreements, representations, warranties, covenants or understandings with respect to the subject matter hereof or thereof other than those expressly set forth herein and therein and (b) this Agreement supersedes all other prior agreements and understandings between the parties with respect to such subject matter.

SECTION 3.10. Severability. If any provision of this Agreement is held to be illegal, invalid or unenforceable under present or future laws effective during the term of this Agreement, such provision shall be fully severable; this Agreement shall be construed and enforced as if such illegal, invalid, or unenforceable provision had never comprised a part of this Agreement; and the remaining provisions of this Agreement shall remain in full force and effect and shall not be affected by the illegal, invalid or unenforceable provision or by its severance from this Agreement. Furthermore, in lieu of each such illegal, invalid or unenforceable provision, there shall be added automatically as a part of this Agreement a provision as similar in terms to such illegal, invalid or unenforceable provision as may be possible and be legal, valid and enforceable.

SECTION 3.11. Table of Contents, Headings and Captions. The table of contents, headings, subheadings and captions contained in this Agreement are included for convenience of reference only, and in no way define, limit or describe the scope of this Agreement or the intent of any provision hereof.

SECTION 3.12. Counterparts. This Agreement and any amendment hereto may be signed in any number of separate counterparts, each of which shall be deemed an original, but all of which taken together shall constitute one Agreement (or amendment, as applicable).

SECTION 3.13. Effectiveness. This Agreement shall be effective immediately prior to the closing of the IPO. If the IPO is not consummated on or prior to July 1, 2010, this Agreement shall automatically be of no force and effect.

SECTION 3.14. No Recourse. This Agreement may only be enforced against, and any claims or cause of action that may be based upon, arise out of or relate to this Agreement, or the negotiation, execution or performance of this Agreement may only be made against the entities that are expressly identified as parties hereto and no past, present or future Affiliate, director,

7

officer, employee, incorporator, member, manager, partner, shareholder, agent, attorney or representative of any party hereto shall have any liability for any obligations or liabilities of the parties to this Agreement or for any claim based on, in respect of, or by reason of, the transactions contemplated hereby.

[Signature Page Follows]

8

IN WITNESS WHEREOF, the parties hereto have caused this Shareholders’ Agreement to be duly executed as of the date first above written.