EXHIBIT 5.1

February 22, 2012

Perfumania Holdings, Inc.

35 Sawgrass Drive, Suite 2

Bellport, New York 11713

Re: Perfumania Holdings, Inc. Registration Statement (File No. 333-179124)

Ladies and Gentlemen:

We have acted as counsel for Perfumania Holdings, Inc., a Florida corporation (the “Company”), in connection with the Registration Statement on Form S-4, File No. 333-179124, as amended (the “Registration Statement”), filed by the Company with the Securities and Exchange Commission (the “Commission”) pursuant to the Securities Act of 1933, as amended (the “Securities Act”). The Registration Statement relates to the proposed issuance by the Company of up to 11,493,795 shares of common stock, par value $0.01 per share, of the Company (the “Shares”) to the shareholders of Parlux Fragrances, Inc. (“Parlux”), a Delaware corporation, pursuant to an Agreement and Plan of Merger, dated as of December 23, 2011, by and between the Company, PFI Merger Corp., a Delaware corporation, and Parlux (the “Merger Agreement”).

We have acted as your counsel in connection with the preparation of the Registration Statement and are familiar with the proceedings of the Board of Directors of the Company in connection with the proposed issuance of the Shares. As to various questions of fact material to our opinion, we have relied upon the representations made in or pursuant to the Merger Agreement and upon certificates and other inquiries of officers of the Company. We are also relying upon the certificates of public officials. We have assumed the genuineness of all signatures, the authenticity of all documents submitted to us as originals and the conformity to original documents of all documents submitted to us as copies. For purposes of this opinion, we have assumed that the execution and delivery of, and the performance of all obligations under, the Merger Agreement have been duly authorized by all requisite action by Parlux and that the Merger Agreement has been duly executed and delivered by Parlux and is a valid and binding agreement of Parlux enforceable against Parlux in accordance with its terms.

The opinion rendered herein is limited to the law of the State of Florida and the federal laws of the United States.

Based upon the foregoing, and subject to the assumptions, qualifications and limitations set forth herein, we are of the opinion that, when issued and delivered in accordance with the terms of the Merger Agreement, the Shares will be duly authorized and validly issued, fully paid and nonassessable.

The foregoing opinion assumes the following: (i) that the Registration Statement has been declared effective by the Commission pursuant to the Securities Act; and (ii) that the required number of the Company’s stockholders will approve the amendment to the Company’s Amended and Restated Articles of Incorporation to increase the number of authorized shares (the “Amendment”) and any necessary filings will be made in accordance with Florida law so that the Amendment becomes effective.

We understand that this letter is to be used in connection with the Registration Statement, as it may be amended from time to time, and hereby consent to the filing of this letter with and as a part of the Registration Statement as so amended, and to the reference to our firm in the prospectus which is a part of the Registration Statement under the heading “Legal Matters.” In giving such consent, we do not hereby admit that we are included within the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations promulgated thereunder.

Very truly yours,

/s/ Edwards Wildman Palmer LLP