Exhibit 99.4

Consent of Peter J. Solomon Company, L.P.

We hereby consent to (i) the inclusion of our opinion letter, dated December 19, 2011, to the Independent Committee of the Board of Directors of Parlux Fragrances, Inc. (“Parlux”) as Annex C to the amended joint proxy statement/prospectus included in the Registration Statement on Form S-4 of Perfumania Holdings, Inc. (“Perfumania”) filed on February 23, 2012 (the “Registration Statement”) relating to the proposed merger of a wholly-owned subsidiary of Perfumania with and into Parlux and (ii) all references to Peter J. Solomon Company in the sections captioned “Summary—Opinions of Financial Advisors”, “The Merger—Background of the Merger”, “The Merger—Parlux Board of Directors’ Recommendation” and “The Merger—Opinions of Financial Advisors to the Parlux Independent Committee”, of the joint proxy statement/prospectus which forms a part of the Registration Statement.

Notwithstanding the foregoing, it is understood that our consent is being delivered solely in connection with the filing of the above-mentioned version of the Registration Statement and that our opinion is not to be used, circulated, quoted or otherwise referred to in whole or in part in any registration statement (including any subsequent amendments to the above-mentioned Registration Statement), joint proxy statement/prospectus or any other document, except in accordance with our prior written consent. In giving such consent, we do not admit that we come within the category of persons whose consent is required under, and we do not admit that we are “experts” for purposes of, the Securities Act of 1933, as amended, and the rules and regulations promulgated thereunder.

PETER J. SOLOMON COMPANY, L.P.

By: /s/ Kenneth Baronoff

New York, New York

February 22, 2012