Exhibit 5.1

March 26, 2013

Francesca’s Holdings Corporation

8760 Clay Road

Houston, Texas 77080

Re: Registration of Securities of Francesca’s Holdings Corporation

Ladies and Gentlemen:

At your request, we have examined the Registration Statement on Form S-3 (the “Registration Statement”) of Francesca’s Holdings Corporation, a Delaware corporation (the “Company”), filed with the Securities and Exchange Commission (the “Commission”) to which this letter is filed as an exhibit in connection with the registration under the Securities Act of 1933, as amended (the “Securities Act”), of the offer and sale of by the Company or selling stockholders to be identified in one or more prospectus supplements from time to time, pursuant to Rule 415 of the General Rules and Regulations of the Commission promulgated under the Securities Act, of an indeterminate amount of shares of the Company’s common stock, par value $0.01 per share (the “Common Stock”).

In connection with the opinion expressed below, we have assumed that, at or prior to the time of delivery of any shares of Common Stock, (i) the Registration Statement has been declared effective and such effectiveness has not been terminated or rescinded, (ii) a prospectus supplement describing the Common Stock offered pursuant to the Registration Statement, to the extent required by applicable law and relevant rules and regulations of the Commission, will be timely filed with the Commission, (iii) the definitive terms of the issuance and sale of the Common Stock will have been duly established in accordance with the authorizing resolutions adopted by the Company’s Board of Directors (or an authorized committee thereof) and in conformity with the Company’s certificate of incorporation and bylaws and applicable law, (iv) the Company will issue and deliver the Common Stock in the manner contemplated by the Registration Statement and the Common Stock will have been authorized and reserved for issuance, in each case, within the limits of the then remaining authorized but unissued and unreserved amounts of such Common Stock, and (v) there has not occurred any change in law affecting the validity or enforceability of the Common Stock. We have also assumed that none of the terms of the Common Stock to be established after the date hereof, nor the issuance and delivery of the Common Stock, nor the compliance by the Company with the terms of the Common Stock will violate any applicable law or public policy or result in a violation of any provision of any instrument or agreement then binding upon the Company or any restriction imposed by any court or governmental body having jurisdiction over the Company.

On the basis of our reliance upon the assumptions in this opinion and our consideration of those questions of law we considered relevant, and subject to the limitations and qualifications in this opinion, we are of the opinion that when an issuance of the Common Stock has been duly authorized by all necessary corporate action on the part of the Company, upon issuance, delivery and payment therefor in an amount not less than the par value thereof and in the manner contemplated by the Registration Statement and/or the prospectus and applicable prospectus supplement(s) and by such corporate action, such shares of Common Stock will be validly issued, fully paid and non-assessable.

The law covered by this opinion letter is limited to the present federal law of the United States, the present law of the State of New York and the current Delaware General Corporation Law (including, as to the Delaware General Corporation Law, the statutory provisions and the reported judicial decisions interpreting those laws).

We hereby consent to the use of this opinion as an exhibit to the Registration Statement and to the reference to this firm under the heading “Legal Matters” in the Prospectus constituting part of the Registration Statement.

Respectfully submitted,

/s/ O’Melveny & Myers LLP