Exhibit 5.1

May 14, 2004

Metrocall Holdings, Inc.
6677 Richmond Highway
Alexandria, Virginia 22306

Dear Sirs:

          We have acted as counsel to Metrocall Holdings, Inc., a Delaware corporation (the “Company”), in connection with the preparation and filing by the Company with the Securities and Exchange Commission (the “Commission”) of Amendment No. 1 to the Registration Statement on Form S-3 (the “Registration Statement”) under the Securities Act of 1933, as amended (the “Securities Act”), which is being filed with the Commission on the date hereof, relating to the offer and sale of up to 625,000 shares of Common Stock, par value $0.01 per share, of the Company (the “Common Stock”), consisting of (i) 500,000 shares of Common Stock that are issued and outstanding (the “Securities”) and (ii) 125,000 shares (the “Warrant Shares”) of Common Stock that are issuable upon exercise of currently outstanding warrants issued by the Company to WebLink Wireless I, L.P. (the “Warrants”).

          In this capacity, we have examined originals, telecopies or copies, certified or otherwise identified to our satisfaction, of such records of the Company and all such agreements, certificates of public officials, certificates of officers or representatives of the Company and others, and such other documents, certificates and corporate or other records as we have deemed necessary or appropriate as a basis for this opinion. As to all matters of fact (including, without limitation, matters of fact set forth in this opinion), we have relied upon and assumed the accuracy of statements and representations of officers and other representatives of the Company and others.

          In our examination, we have assumed the genuineness of all signatures, the authenticity of all documents submitted to us as originals, the conformity to original documents of all documents submitted to us as certified or photostatic copies and the authenticity of the originals of such latter documents.

          We are attorneys admitted to practice in the State of New York and the opinion expressed below is limited to the laws of the State of New York and the General Corporation Law of the State of Delaware.

          Based upon the foregoing, and having regard for such legal considerations as we deem relevant, we are of the opinion that (i) the Securities have been validly issued and are fully

paid and non-assessable, and (ii) the Warrant Shares issuable upon exercise of the Warrants will be, if and when issued upon exercise of the Warrants in the manner provided in the Warrants, validly issued, fully paid and non-assessable.

          We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the reference to this firm appearing under the heading “Legal Matters” in the Registration Statement and the Prospectus which forms a part of the Registration Statement. In giving such consent, we do not thereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission promulgated thereunder.

Very truly yours,

/s/ Schulte Roth & Zabel LLP