Exhibit 23.1

CONSENT OF INDEPENDENT ACCOUNTANTS

We hereby consent to the incorporation by reference in the Registration Statements on Form S-8 (No. 333-106044 and 333-109409) of Metrocall Holdings, Inc. of our report dated February 26, 2004 relating to the financial statements of Arch Wireless, Inc. as of December 31, 2003 and December 31, 2002 and for the period from January 1, 2002 to May 31, 2002 and for the period from June 1, 2002 to December 31, 2002, and for the year ended December 31, 2003, which appears in this Current Report on Form 8-K of Metrocall Holdings, Inc.

/s/ PRICEWATERHOUSECOOPERS LLP

Boston, Massachusetts
May 14, 2004