Exhibit 99.1

For Immediate Release:
Tuesday, December 2, 2003

Metrocall Contact:
Timothy J. Dietz
Director, Corporate Communications
& Investor Relations
(703) 660-6677x6231
dietzt@metrocall.com

Metrocall Announces $20 Million Preferred Stock Redemption

Declares Dividend on Preferred Stock

     Alexandria, VA, Tuesday, December 2, 2003 — Metrocall Holdings, Inc. (OTCBB: MTOH), a leading provider of paging and two-way wireless messaging, today announced that on January 6, 2004, it will make a $20 million redemption of 1,793,411 shares, representing approximately 43%, of its outstanding series A preferred stock (series A preferred). The per share redemption price will be approximately $11.15. Following this redemption, the Company will have redeemed approximately 3.6 million, or approximately 60%, of the aggregate 6 million series A preferred shares issued in connection with its October 2002 reorganization. This voluntary redemption of shares will be completed using $20 million in cash balances generated from operations. Metrocall’s current cash balances are in excess of $32 million. Shares will be redeemed on a pro-rata basis from all holders of record on December 2, 2003. After the redemption, Metrocall will have approximately 2.4 million shares of its series A preferred stock outstanding with an aggregate liquidation preference of approximately $26.7 million.

     The payment follows an initial $20 million redemption of series A preferred completed on September 30, 2003 and the retirement in full of approximately $81.5 million aggregate principal amount of Metrocall’s long-term debt securities completed on June 30, 2003.

     Additionally, Metrocall’s board of directors has declared a dividend on the series A preferred stock of approximately $0.42 per share, payable December 31, 2003, to holders of record on December 15, 2003. Please refer to the Company’s most recent report on Form 10-Q, annual report on Form 10-K and proxy statement for details on these securities.

     “We are pleased with the progress we have made over the last year,” stated Vincent D. Kelly, Metrocall President & CEO. “During 2003 we paid off all of our long-term debt securities, have made significant progress in redeeming our preferred stock and announced the asset acquisition of Weblink Wireless. During 2004 we expect to redeem the remaining 2.4 million shares of outstanding series A preferred stock by continuing our focus on cash flow generation.”

About Metrocall Wireless, Inc.
Metrocall Wireless, Inc., headquartered in Alexandria, Virginia, is a leading provider of paging products and other wireless services to business and individual subscribers. In addition to its reliable, nationwide one-way networks, Metrocall’s two-way network has the largest high-powered terrestrial ReFLEX footprint in the United States with roaming partners in Canada, Mexico, the Caribbean, Central and South America. Metrocall Wireless is the preferred ReFLEX wireless data network provider for many of the largest telecommunication companies in the United States that source virtual network services and resell under their own brand names. In addition to traditional numeric, one-way text and two-way paging, Metrocall also offers wireless e-mail solutions, as well as mobile voice and data services through AT&T Wireless and Nextel. Also, Metrocall offers Integrated Resource Management Systems with wireless connectivity solutions for medical, business, government and other campus environments. Metrocall focuses on the business-to-business marketplace and supports organizations of all sizes, with a special emphasis on the medical and government sectors. For more information on Metrocall please visit our Web site and on-line store at www.metrocall.com or call 800-800-2337.

Safe Harbor Statement Under the Private Securities Litigation Reform Act of 1995
This press release includes “forward-looking statements,” within the meaning of the federal securities laws, that involve uncertainties and risks. These include statements regarding events or developments that Metrocall Holdings expects or anticipates will occur in the future. A number of risks and uncertainties could cause actual results, events, and developments to differ from expectations. Please refer to Metrocall’s most recent quarterly report on Form 10-Q and annual report on Form 10-K, and any subsequently filed reports on Form 10-Q and Form 8-K, as well as its other filings with the Securities and Exchange Commission, for a complete discussion of these and other important factors that could cause actual results to differ materially from those projected by these forward-looking statements.