STOCKHOLDERS AGREEMENT

Exhibit 10.12

STOCKHOLDERS AGREEMENT

STOCKHOLDERS AGREEMENT dated as of December 23, 2011 (this “Agreement”), by and among Perfumania Holdings, Inc., a Florida corporation (the “Company”), Rene Garcia, a stockholder of the Company (“Stockholder”), and the persons and trusts related to Stockholder listed on the signature page hereof (together with Stockholder, the “Stockholder Parties”).

RECITALS

A. The Stockholder Parties are the beneficial owners of shares of Company Common Stock and shares of the Common Stock of Parlux Fragrances, Inc., a Delaware corporation (“Parlux”), including both outstanding shares of Parlux and the Company and shares issuable upon exercise of warrants to purchase such shares.

B. Concurrently with the execution of this Agreement, (i) the Company is entering into an Agreement and Plan of Merger (the “Merger Agreement”) with Parlux and PFI Merger Corp. pursuant to which, among other matters, as of the Effective Time, shares of common stock of Parlux will be converted into shares of Company Common Stock and options and warrants to acquire common stock of Parlux will be converted into options and warrants to acquire Company Common Stock, and (ii) Stockholder, the Company and/or Parlux (together with other parties) are entering into the Letter Agreement, the Licensor Warrant Amendment and a letter agreement described in Section 5.5(c) of the Merger Agreement.

C. It is a condition to the Company’s willingness to enter into certain of the agreements referred to in Clause B that the Stockholder Parties enter into this Agreement, and the Stockholder Parties wish to enter into and be bound hereby in order to induce the Company to enter into such agreements.

NOW, THEREFORE, in consideration of the premises and the covenants herein and intending to be legally bound, the parties agree as follows:

1. Definitions. Capitalized terms used herein that are undefined shall have the meanings set forth in the Merger Agreement. As used in this Agreement, the following terms have the following respective meanings:

“beneficial owner” is used with the same meaning as in Rule 13d-3 under the Exchange Act;

“Company Common Stock” means the common stock, $.01 par value, of the Company;

“Exchange Act” means the Securities Exchange Act of 1934, as amended;

“Nussdorfs means Stephen Nussdorf, Glenn Nussdorf and Arlene Nussdorf;

“Nussdorfs Group” means the Nussdorfs or any member of the Nussdorfs’ immediate family, or to a trust for the benefit of the Nussdorfs or any member of the Nussdorfs’ immediate family, or pursuant to the laws of descent and distribution;

“Person” means an individual or a corporation, partnership, limited liability company, association, trust, or any other entity or organization;

“Significant Matter” means whether in a single or series of transactions (i) a merger, reorganization, share exchange, consolidation, business combination, joint venture, partnership,

recapitalization, dissolution, liquidation or similar transaction involving the Company constituting more than fifty percent (50%) or more of the assets, revenues or earnings of the Company, (ii) an acquisition of assets of the Company equal to more than fifty percent (50%) of the consolidated assets of the Company, (iii) an acquisition of more than 50% of the outstanding Company Common Stock, (iv) the issuance of Company Common Stock that after giving effect to such issuance represents more than fifty percent (50%) of the outstanding Company Common Stock, or (v) a tender offer or exchange offer that, if consummated, would result in any person or “group” (as defined under Rule 13(d) of the Exchange Act) beneficially owning more than fifty (50%) of the outstanding Company Common Stock, other than the Nussdorf Group;

“Term” means the period from and including the Effective Time until the earlier of (a) the fourth (4^th) anniversary of the date hereof and (b) the date on which the Nussdorf Group collectively ceases to be the beneficial owners of at least 33 1/3% of the total number of outstanding shares of Company Common Stock; and

“Voting Shares,” as of any date, means all shares of Company Common Stock of which the Stockholder Parties are, individually or jointly, the beneficial owners, including without limitation, all shares of Company Common Stock with respect to which any of the Stockholder Parties becomes a beneficial owner following the date hereof.

(a) In every vote of the Company’s stockholders taken from time to time during the Term with respect to any Significant Matter publicly opposed by the Board of Directors of the Company (the “Board”) or as to which the Board shall have recommended a vote against, whether at any meeting of the stockholders of the Company, at any adjournment or postponement thereof, or pursuant to an action or approval by written consent, the Stockholder Parties shall not vote or cause to be voted the Voting Shares in favor of such Significant Matter.

(b) In every vote of the Company’s stockholders taken from time to time during the Term with respect to the election of one or more directors not recommended or nominated by the Board or the approval of the exercise of voting rights with respect to Company Common Stock acquired pursuant to a Significant Matter that shall not have been recommended by the Board for approval, whether at any meeting of the stockholders of the Company, at any adjournment or postponement thereof, or pursuant to an action or approval by written consent, the Stockholder Parties shall not vote or cause to be voted the Voting Shares in favor of any such director or the exercise of such voting rights.

(b) The Stockholder Parties shall not, during the Term, (i) enter into any agreement or understanding with, or give any proxy to, any Person to vote or have voted or give instructions inconsistent with Section 2(a), (ii) deposit any of the Voting Shares into a voting trust or enter into a voting agreement or similar contract with respect to any of the Voting Shares, unless the voting of the Voting Shares pursuant thereto shall be in accordance with Section 2(a), or (iii) agree with any Person to take any of such actions.

(c) During the Term hereof, the Stockholder Parties shall promptly notify the Company upon the acquisition of beneficial ownership of any additional Voting Shares by any of them.

(a) During the Term, a Stockholder Party shall be expressly permitted, directly or indirectly to transfer, sell, offer, exchange, assign, pledge or otherwise dispose of or encumber (“Transfer”) any of

2

the Voting Shares (including any option, warrant or other right exercisable for, or any other security or instrument convertible into, exchangeable for or that may be settled for, any Voting Share) or enter into any contract, option or other agreement with respect to, or consent to, a Transfer of, any of the Voting Shares or the Stockholder Party’s voting or economic interest therein, other than to

(i) a Transfer to or with any transferee (A) which filed with the Securities and Exchange Commission a Schedule 13D under the Exchange Act with respect to the Company which indicates that such transferee is proposing, or may propose, a Significant Matter which the Company has indicated would not be approved by the Board or is acquiring the Voting Shares or rights therein with the purpose or the effect of changing or influencing the control of the Company, or in connection with or as a participant in any transaction having such purpose or effect, or (B) with respect to which a Stockholder Party is aware of facts would conclude that such transferee is acquiring the Voting Shares or rights therein with the purpose or the effect of changing or influencing the control of the Company, or in connection with or as a participant in any transaction having such purpose or effect, based solely on the written representations and warranties made such transferee in connection with such Transfer ; or

(ii) pursuant to a Significant Transaction that has not been approved, recommended or consented to by the Board.

4. Standstill. During the Term, none of the Stockholder Parties or any of their affiliates shall, individually or collectively, directly or indirectly, unless specifically permitted in writing in advance by the Board:

(a) acquire, or agree, offer, seek or propose to acquire ownership (including, but not limited to, beneficial ownership) of more than 28% of the outstanding Company Common Stock or any options, warrants, or other rights to acquire such ownership (including from a third party), it being understood and agreed that the foregoing shall not preclude any Stockholder from exercising any option, warrant or other derivative security;

(b) make, or in any way participate in, directly or indirectly, any “solicitation” of “proxies” (as such terms are defined or used in Regulation 14A under the Exchange Act) or become a “participant” in any “election contest” (as such terms are defined or used in Rule 14a-11 under the Exchange Act) with respect to the Company, or initiate, propose or otherwise solicit stockholders of the Company for the approval of one or more stockholder proposals with respect to the Company, or induce or attempt to induce any other person to initiate any stockholder proposal, or seek to advise or influence any person or entity with respect to the voting of any voting securities of the Company;

(c) alone or in concert with others, seek to control the management, Board, policies or affairs of the Company or any of its subsidiaries or affiliates, or solicit, propose, seek to effect or negotiate with any other person with respect to any Significant Transaction, or announce or disclose an intent, purpose, plan or proposal with respect to the Company or any of its subsidiaries or any securities issued by the Company inconsistent with the provisions of this Section 4, including an intent, purpose, plan or proposal that is conditioned on or would require the Company to waive the benefit of or amend any provision of this Section 4, or assist, participate in, facilitate or encourage or solicit any effort or attempt by any person to do or seek to do any of the foregoing;

(d) nominate any person for election by the stockholders of the Company as a director of the Company who is not nominated by the then-incumbent directors, or propose any matter to be voted upon by the stockholders of the Company;

3

(e) form, join in or in any way participate in a partnership, syndicate or other “group” (as such term is used in Section 13(d)(3) of the Exchange Act) or assist others, directly or indirectly, in connection with any of the foregoing; or

(f) disclose any intention, plan or arrangement inconsistent with the foregoing, or take any action that would require the Company to make a public announcement regarding the possibility of any of the events described in the foregoing clauses (a) through (e).

5. Stop Orders. The Stockholder Parties acknowledge and agree that the Company may, during the Term, place and maintain stop transfer orders with its transfer agent respect the Voting Shares in order to ensure compliance with the terms hereof.

6. Representations, Warranties and Covenants of the Stockholder Parties. Each Stockholder Party, severally, and not jointly, represents and warrants to the Company that:

(a) Ownership of Voting Shares. Schedule 1 hereto lists all of the Voting Shares, in whatever form, including those issuable upon exercise, exchange, conversion or settlement of options, warrants or other rights, of which such Stockholder Party is the beneficial owner and that, except pursuant to this Agreement, there are no options, warrants or other rights, agreements, voting trusts, voting agreements or other arrangements or commitments of any character relating to the pledge, disposition or voting of any Voting Shares of which such Stockholder Party is the beneficial owner;

(b) No Conflict. The execution and delivery of this Agreement by the Stockholder Party does not, and the performance of this Agreement by the Stockholder Party will not: (i) conflict with or violate any legal requirement, order, decree or judgment applicable to the Stockholder Party or by which the Stockholder Party is bound or affected; or (ii) result in any breach of or constitute a default (with notice or lapse of time, or both) under, or give to others any rights of termination, amendment, acceleration or cancellation of, or result in the creation of an encumbrance on or otherwise affecting any of the Voting Shares pursuant to, any contract to which the Stockholder Party is a party or by which the Stockholder Party is bound or affected. The execution and delivery of this Agreement by the Stockholder Party do not, and the performance of its obligations under this Agreement by the Stockholder Party will not, require any consent of any Person not a party to this Agreement;

(c) Enforceability. The Stockholder Party has all requisite power and capacity to execute and deliver this Agreement and to perform its obligations hereunder and thereunder. This Agreement has been duly executed and delivered by the Stockholder Party and, assuming the due authorization, execution and delivery of this Agreement by the Company, each constitute the legal, valid and binding obligations of the Stockholder Party, enforceable against the Stockholder Party in accordance with their respective terms, subject to (i) laws of general application relating to bankruptcy, insolvency and the relief of debtors, and (ii) rules of law governing specific performance, injunctive relief and other equitable remedies; and

(d) Further Assurances. The Stockholder Party hereby covenants and agrees to cooperate fully with Company and to execute and deliver any additional documents in form and substance acceptable to the Stockholder Party necessary or desirable and to take such further actions, in the reasonable opinion of Company, necessary or desirable to carry out the intent of this Agreement.

7. Effectiveness; Termination. For sake of clarity, unless and until the Effective Time, none of the provisions of this Agreement (including without limitation Sections 2, 3 and 4) shall be of any force or effect. This Agreement shall terminate and be of no further force or effect as of the end of the Term;

4

provided that termination hereof shall not affect any party’s rights with respect to any breach hereof during the Term.

(a) Entire Agreement; Amendments. This Agreement (including the documents and the instruments referred to herein, including without limitation, the Merger Agreement, the Letter Agreement, the Licensor Warrant Amendment and a letter agreement described in Section 5.5(c) of the Merger Agreement) (a) constitutes the entire agreement, superseding all prior agreements, negotiations, arrangements and understandings, written or oral, between the parties with respect to the subject matter hereof, and (b) this Agreement may not be amended, modified, or supplemented except upon the execution and delivery of a written agreement executed by the Company and the Stockholder Parties.

(b) Notices. All notices, requests, consents, and other communications under this Agreement shall be in writing and shall be deemed delivered when received or, if earlier, (i) three business days after being sent by registered or certified mail, return receipt requested, postage prepaid or (ii) one business day after being sent via a reputable nationwide overnight courier service guaranteeing next business day delivery, in each case to the intended recipient as set forth below: If to the Company, to 35 Sawgrass Drive, Suite 2, Bellport, New York 11713, Attention: Chief Executive Officer, with a copy to Edwards Wildman Palmer LLP, 750 Lexington Avenue, 8^th Fl., New York, NY 10022; Attention: Patricia L. Kantor, Esq.; or if to any Stockholder Party, to Rene Garcia 1608 NW 84th Avenue, Miami, FL 33126, with a copy to Littman Krooks LLP, 655 Third Avenue, 20^th floor, New York, NY 10017; Attention: Mitchell C. Littman, Esq. Any party may change the address to which notices, requests, consents or other communications hereunder are to be delivered by giving the other parties notice in the manner set forth in this Section.

(c) Counterparts. This Agreement may be executed in one or more counterparts (whether delivered by facsimile or otherwise), each of which shall be considered one and the same agreement.

(d) Severability. Any term or provision of this Agreement that is held by a court of competent jurisdiction or other authority to be invalid, void or unenforceable in any situation in any jurisdiction shall not affect the validity or enforceability of the remaining terms and provisions hereof or the validity or enforceability of the invalid, void or unenforceable term or provision in any other situation or in any other jurisdiction. If the final judgment of a court of competent jurisdiction or other authority declares that any term or provision hereof is invalid, void or unenforceable, the parties agree that the court making such determination shall have the power to and shall, subject to the discretion of such court, reduce the scope, duration, area or applicability of the term or provision, to delete specific words or phrases, or to replace any invalid, void or unenforceable term or provision with a term or provision that is valid and enforceable and that comes closest to expressing the intention of the invalid or unenforceable term or provision.

(e) Governing Law. Except to the extent the Florida Business Corporation Act controls the interpretation or construction hereof, this Agreement shall be deemed to be made in, and in all respects shall be interpreted, construed and governed by and in accordance with the internal laws of, the State of New York, without regard to the conflicts of law principles thereof that would cause the application of the laws of any jurisdiction other than the internal laws of State of New York.

(f) Enforcement. The parties agree that irreparable damage 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. It is accordingly agreed that the parties shall be entitled to seek an injunction or injunctions to prevent breaches of this Agreement and to enforce specifically the terms and provisions of

5

this Agreement in the United States District Court for the Eastern District of New York or in New York Supreme Court sitting in Suffolk County, New York, without bond or other security being required, this being in addition to any other remedy to which they are entitled at law or in equity. The parties hereby agree that service of any process, summons, notice or document by registered mail to the respective addresses set forth in Section 8(b) shall be effective service of process for any suit or proceeding in connection with this Agreement or the transactions contemplated hereby.

(g) Assignment. Neither this Agreement nor any of the rights, interests or obligations hereunder shall be assigned by any of the parties to this Agreement (whether by operation of law or otherwise) without the prior written consent of the Company and the Stockholder Parties. Subject to the preceding sentence, this Agreement will be binding upon, inure to the benefit of and be enforceable by the parties and their respective successors and assigns.

[Signatures on the following page]

6

IN WITNESS WHEREOF, the parties have caused this Agreement to be duly executed on the date and year first written above.

[Signature Page to Stockholders Agreement]

[Signature Page to Stockholders Agreement]

SCHEDULE 1

Voting Shares