Exhibit 10.4

Execution Copy

VOTING AGREEMENT

THIS VOTING AGREEMENT (this “Agreement”) is made and executed as of the 22nd day of May, 2009 (the “Effective Date”), by, between and among Nature’s Sunshine Products, Inc., a Utah corporation organized under the Utah Revised Business Corporation Act (“URBCA”) (the “Company”); Paradigm Capital Management, Inc., a New York corporation (the “Shareholder”); Kristine F. Hughes, Pauline Hughes Francis and Eugene L. Hughes (collectively, the “Hughes Parties”).

RECITALS

A. As of the date of this Agreement, the Shareholder Beneficially Owns 1,573,737 shares of common stock of the Company, representing approximately 10.2% of the issued and outstanding common stock of the Company.

B. The Company and the Shareholder have agreed that, among other things, if the Company’s Board of Directors (the “Board”) is reconstituted as set forth herein, the Shareholder will vote its shares for the election of the members of the reconstituted Board in the next annual meeting of the Company’s shareholders. The parties desire to memorialize their arrangement in this Agreement.

AGREEMENT

NOW, THEREFORE, in consideration of the foregoing premises and mutual covenants contained herein, and for other good and valuable consideration, the receipt and sufficiency of which are acknowledged, the parties agree as follows:

1. Certain Definitions. For purposes of this Agreement:

1.1 “Affiliate” has the meaning set forth in Rule 12b-2 promulgated by the SEC under the Exchange Act.

1.2 “Beneficial Owner,” “Beneficial Ownership” and “Beneficially Own” have the same meaning as set forth in Rule 13d-3 promulgated by the SEC under the Exchange Act.

1.3 “SEC” means the Securities and Exchange Commission.

1.4 “Voting Shares” means (i) all equity securities of the Company Beneficially Owned by the Shareholder or the Hughes Parties, respectively, as of the date of this Agreement less any such shares disposed of by the Shareholder or the Hughes Parties, respectively, after the Effective Date in compliance with Section 6.9 and (ii) all additional equity securities of the Company of which the Shareholder or the Hughes Parties may acquire Beneficial Ownership during the period from the date of this Agreement through the Voting Agreement Termination Date (hereinafter defined).

2. Distribution of Section 14(f) Statement. Within three (3) business days following the execution of this Agreement, the Company will distribute to its shareholders the information statement (the “Section 14(f) Statement”) required by Section 14(f) of the Securities Exchange Act of 1934, as amended (the “Exchange Act”) and Rule 14f-1 promulgated pursuant thereto.

3. Board Changes. The following actions shall be effective immediately following the tenth (10th) day after the Company distributes to its shareholders the Section 14(f) Statement:

3.1 The number of directors constituting the Board shall be increased to eight (8) in accordance with Section 3.2 of the Bylaws of the Company and one of the newly created vacancies shall be assigned to Class II and the other newly created vacancy shall be assigned to Class III in accordance with Article IX of the Company’s Restated Articles of Incorporation.

3.2 The resignations of Robert K. Bowen, Larry K. Deppe, Pauline Hughes Francis, and Eugene L. Hughes as members of the Board attached as Exhibits A-1 though A-4 and previously tendered to the Company shall become effective in accordance with their terms leaving Kristine F. Hughes as the sole remaining incumbent director assigned to Class III and creating four vacancies on the Board in addition to the fifth vacancy previously created by Franz Cristiani’s prior resignation as a director effective March 1, 2007 and the sixth and seventh vacancies created by the increase in the size of the Board of directors as described in Section 3.1.

3.3 Each of the seven persons identified on Exhibit B as an “Appointee” (collectively, the “Appointees”) shall be appointed, pursuant to Section 3.10 of the Bylaws of the Company and Section 16-10a-810(1)(c) of the URBCA, to fill the seven vacancies on the Board and serve as directors until the next shareholders’ meeting at which directors are elected and until their respective successors shall be duly elected and qualified, unless they resign, are removed or are otherwise disqualified from serving as a director of the Company, and each such Appointee shall serve in the class set forth next to his or her name on Exhibit B.

4. Annual Meetings of the Shareholders. The Company shall use commercially reasonable efforts to hold an annual meeting of the shareholders no later than December 31, 2009 unless otherwise agreed by the then serving Board of Directors (the “Next Annual Meeting”).

5. Voting Agreement.

5.1 The Shareholder and the Hughes Parties agree that from the date of this Agreement and until immediately following the Next Annual Meeting or any adjournment or postponement thereof or December 31, 2009, whichever is earlier (the “Voting Agreement Termination Date”), at the Next Annual Meeting or any other meeting of shareholders of the Company or any adjournment or postponement thereof, and on every action or approval by written consent of the shareholders of the Company, if any, the Shareholder and the Hughes Parties will take the following actions to effect the intent of this Agreement:

5.1.1 Vote all of the Voting Shares in favor of the Director nominees listed in Exhibit B, in those classes and for the terms listed in Exhibit B (unless

they or any of them prior thereto shall have resigned or been removed as a director or otherwise shall have refused to stand for election);

5.1.2 Appear, or cause the holder of record of any Voting Shares on any applicable record date to appear at such meeting or otherwise cause the Voting Shares to be counted as present for purposes of establishing a quorum; and

5.1.3 None of the Shareholder or the Hughes Parties shall take any position, make any statement or take any action inconsistent with the foregoing.

5.2 In order to secure the performance of the Shareholder’s and the Hughes Parties’ obligations under this Agreement, each such party hereby irrevocably grants a proxy appointing Kristine F. Hughes and Pauline Hughes Francis each as such party’s attorney-in-fact and proxy, with full power of substitution, for and in its name, place and stead, to vote, express consent or dissent, or otherwise to utilize such party’s Voting Shares SOLELY to vote for those nominees and in those classes as are specified and listed on Exhibit B at the Next Annual Meeting or any other meeting of shareholders of the Company or any adjournment or postponement thereof prior to the Voting Agreement Termination Date, in each case in a manner consistent with Section 5.1. Each of the Shareholder and the Hughes Parties hereby represents and warrants that any proxies heretofore given in respect of the Voting Shares are not irrevocable and that any such proxies are hereby revoked including, without limitation, any proxy granted by the Shareholder to Prescott Group Aggressive Small Cap Master Fund, G.P., Phil Frolich or Duminda DeSilva, or any of their Affiliates. Each such party hereby affirms that THE PROXY AND POWER OF ATTORNEY SET FORTH IN THIS AGREEMENT IS IRREVOCABLE AND COUPLED WITH AN INTEREST and SHALL EXPIRE ON THE VOTING AGREEMENT TERMINATION DATE.

6. Standstill. From and after the Effective Date until the Voting Agreement Termination Date, the Shareholder and the Hughes Parties and their respective agents, employees, officers, directors, managers, control persons, representatives, successors, assigns, parent corporations, subsidiaries, Affiliates and all other persons acting in concert with or under the control or direction of any of the Shareholder or the Hughes Parties shall not, directly or indirectly, in any manner without the prior consent of the Company:

6.1 advise, encourage, support or influence any person with respect to the voting or disposition of any shares of the company contrary to the terms of this Agreement;

6.2 grant a proxy with respect to the voting of the shares of the Company to any person other than as to matters not contemplated in the proxy set forth in Section 5.2;

6.3 deposit any shares of the Company in a voting trust or enter into any other arrangement or agreement with respect to the voting thereof other than as to matters not contemplated in the proxy set forth in Section 5.2;

6.4 take any action, alone or in concert with any other person, advise, finance, assist or participate in or encourage any person to take any action which is prohibited to be taken by such party pursuant to this Agreement, or make any investment in or enter into any

arrangement with, any other person that engages, or offers or proposes to engage in any of the foregoing;

6.5 pursuant to the URBCA, directly or indirectly (or assist any other person or entity directly or indirectly), make a demand or seek a court order that the Company hold a special meeting of the shareholders, or in lieu thereof an annual meeting of the shareholders, for any purpose including without limitation the purpose of electing directors;

6.6 make or cause to be made, any public statement or announcement that relates to and constitutes an ad hominem attack on, or relates to or otherwise disparages, the Company, its officers, directors, employees, or any person who has served as an officer, director or employee of the Company;

6.7 recommend or request or induce or attempt to induce any other person to take any of the foregoing actions, or seek to advise, encourage or influence any person with respect to the voting of (or the execution of a written consent in respect of) any shares of the Company, except in accordance with the terms of this Agreement;

6.8 propose any other slate of directors for election at the Next Annual Meeting other than the individuals listed on Exhibit B (unless they or any of them prior thereto shall have resigned or been removed as a director or otherwise shall have refused to stand for election);

6.9 assign or sell, or offer to assign or sell, any Voting Shares in a private resale transaction or make a gift of any Voting Shares unless the recipient of such shares agrees to be bound by this Agreement in the same manner the Shareholder is bound hereto including without limitation the provisions of Sections 5, 6 and 9 of this Agreement;

6.10 disclose publicly or privately, in a manner that could reasonably be expected to become public, any intention, plan or arrangement inconsistent with the foregoing; or

6.11 take any action challenging the validity or enforceability of this Agreement.

7. Representations and Warranties of the Shareholder. The Shareholder represents and warrants to the Company that (a) it Beneficially Owns the number of Voting Shares as set forth in Recital A, and does not own, or have the right to acquire, any economic or voting rights with respect to the Company’s securities except with respect to the Voting Shares of the Shareholder; (b) it has all requisite power and authority to execute, deliver and perform this Agreement; (c) this Agreement constitutes a valid and binding obligation of the Shareholder, enforceable in accordance with its terms; and (d) no consent, approval, waiver, authorization or filing, which has not already been obtained or is otherwise contemplated by this Agreement, is necessary for the execution, delivery and performance by the Shareholder of this Agreement.

8. Representations and Warranties of the Company and Hughes Parties. The Company and the Hughes Parties severally hereby represent and warrant to the Shareholder that (a) the Hughes Parties Beneficially Own an aggregate of 3,187,623 Voting Shares, and do

not own or have the right to acquire any economic or voting rights with respect to the Company’s securities except with respect to the Voting Shares of the Hughes Parties; (b) they have all requisite power and authority to execute, deliver and perform this Agreement; (c) this Agreement constitutes a valid and binding obligation of the Company and the Hughes Parties, enforceable in accordance with its terms; and (d) no consent, approval, waiver, authorization or filing, which has not already been obtained or is otherwise contemplated by this Agreement, is necessary for the execution, delivery and performance by the Company or the Hughes Parties of this Agreement.

9. Additional Covenants. Until the Voting Agreement Termination Date, the Company shall and the Shareholder and the Hughes Parties shall cause the Company to:

9.1 propose to be elected at the Next Annual Meeting all directors identified on Exhibit B, except to the extent any such director prior thereto shall have resigned, been removed as a director or otherwise shall have refused to stand for election at the Next Annual Meeting;

9.2 take all reasonable actions necessary to cause the terms of the directors assigned to Class I, Class II and Class III as specified on Exhibit B to terminate only as also specified on Exhibit B; and

9.3 refrain from increasing or decreasing the size of the Board from eight members.

10. Miscellaneous Provisions. The following provisions are also an integral part of this Agreement:

10.1 Public Disclosures. On or before the date upon which the Company shall be required to file with the SEC a Current Report on Form 8-K with respect to this Agreement and the Company actions contemplated herein, the Company shall issue a press release in a form provided to the Hughes Parties and the Shareholder prior to such issuance. Except as set forth in this Agreement, none of the Company, the Shareholder or the Hughes Parties shall make any public announcement or statement concerning this Agreement or public comment on this Agreement; provided, however, that any party may make such announcement, statement or comment concerning this Agreement as is required by law, including, without limitation, any filing required by applicable rules or regulations of the SEC, or the rules of any stock exchange; provided, further, that the Company may respond to shareholder, analyst and media inquiries regarding the terms of the Agreement. The Company shall disclose this Agreement in a Current Report on Form 8-K filed with the SEC in the time period required by applicable law and file this Agreement as an Exhibit to such Form 8-K.

10.2 Successors and Assigns. This Agreement shall bind and benefit the parties’ respective heirs, successors, assigns, affiliates, officers, directors, agents, servants, employees and attorneys. No party shall assign this Agreement or any rights or obligations hereunder without, with respect to the Shareholder, the prior written consent of the Company, and with respect to the Company and the Hughes Parties, the prior written consent of the Shareholder.

10.3 No Assignment of Claims. The parties represent that they have not assigned or otherwise transferred any interests, rights, causes of action, or claims they have, may have, or could have had against one another.

10.4 Captions; Interpretation. The captions used in this Agreement are inserted for reference purposes only and shall not be deemed to define, limit, extend, describe, or affect in any way the meaning, scope or interpretation of any of the terms of this Agreement or its intent. As the context requires, the singular shall include the plural, and vice versa; and the masculine shall include the feminine and neuter, and vice versa.

10.5 Counterparts. This Agreement may be signed in any number of counterparts with the same effect as if the signatures upon any counterpart were upon the same instrument. All signed counterparts shall be deemed to be one original. A facsimile transmittal bearing a photocopied signature shall be deemed an original.

10.6 Severability. The provisions of this Agreement are severable and should any provision be void, voidable, unenforceable or invalid, such provision shall not affect the remaining provisions of this Agreement.

10.7 Waiver of Breach. Any waiver by any party of any breach of any kind by the other, whether direct or implied, shall not be construed as a continuing waiver of, or consent to, any subsequent breach of this Agreement.

10.8 No Concession of Liability. This Agreement shall not in any event constitute, be construed or deemed a concession or admission of any liability or wrongdoing of any of the parties.

10.9 Entire Agreement; Amendment. With respect to the subject matter of this Agreement, this Agreement constitutes the entire agreement among the parties, and it may not be altered, modified or amended except by written agreement signed by the Company and the Shareholder. With respect to the subject matter of this Agreement, and except as expressly provided in the Agreement, all prior and contemporaneous agreements, arrangements and understandings among the parties are hereby superseded and rescinded.

10.10 Governing Law; Venue. This Agreement shall be interpreted, construed and enforced according to the substantive laws of the State of Utah. Any dispute arising out of this Agreement, or the breach thereof, shall be brought exclusively in any state or federal court of competent jurisdiction in the State of Utah, the parties expressly consenting to jurisdiction and venue in such courts.

10.11 Costs. Each party shall bear its own costs and expenses in connection with the negotiation, execution and performance of this Agreement or the events or actions referred to herein.

10.12 Attorney Fees. If any party shall breach its obligations under this Agreement, the party not in breach shall be entitled to recover its costs, expenses and reasonable attorney fees from the breaching party, whether such sums be expended with or without suit and

regardless of the forum (including but not limited to recourse in connection with any bankruptcy case, insolvency proceeding, or arbitration proceeding).

10.13 Cumulative Remedies; Specific Performance. The rights and remedies of the parties shall be construed cumulatively, and none of such rights and remedies shall be exclusive of, or in lieu or limitation of, any other right, remedy or priority allowed by law, unless specifically set forth herein. The parties acknowledge that irreparable harm would occur in the event that any of the provisions of this Agreement were not performed in accordance with their specific terms or were otherwise breached and that legal remedies alone for breach of this Agreement may be inadequate. The parties further acknowledge that any party by whom this Agreement is enforceable shall be entitled to institute and prosecute proceedings, either at law or in equity, to seek specific performance of the terms and conditions of this Agreement, to obtain injunctive relief, or to obtain any other appropriate relief or remedy. Any requirements for securing or posting of any bond in connection with such remedies are hereby waived.

10.14 Notice. Any notice or other communication required or permitted by this Agreement shall be deemed to have been received (a) upon personal delivery or actual receipt thereof or (b) two business days after such notice shall be faxed to the party at the fax number stated below (or such other number as the party shall provide in writing) or deposited in the United States mail, postage prepaid and certified (return receipt requested) and addressed to the party at the address set forth below (or such other address as the party shall provide in writing):

If to the Company, at the following addresses:

Jamon A. Jarvis

General Counsel, Chief Compliance Officer

NATURE’S SUNSHINE PRODUCTS, INC.

75 East 1700 South

Provo, Utah 84606

Fax: 801.342.4555

Nolan S. Taylor

DORSEY & WHITNEY LLP

136 South Main Street, Suite 1000

Salt Lake City, Utah 84101

Fax: 801.933.7373

If to the Shareholder, at the following addresses:

Candace King Weir

Paradigm Capital Management, Inc.

9 Elk Street

Albany, New York 12207

Fax: 518-351-3550

David I. Ferber, Esq.

Ferber Chan Essner & Coller, LLP

530 Fifth Avenue, 23rd Floor

New York, New York 10036

Fax: 212-944-7630

If to the Hughes Parties, at the following addresses:

Pauline Hughes Francis

P.O. Box 1007

Salem, UT 84653

Fax: 801.423.3130

Eugene L. Hughes

P.O. Box 51755

Provo, UT 84605

Kristine F. Hughes