For Immediate Release:
Tuesday, September 30, 2003

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

Metrocall Redeems 30 Percent of
Outstanding Preferred Stock

     Alexandria, VA, Tuesday, September 30, 2003 - Metrocall Holdings, Inc. (OTCBB: MTOH), the nation’s second largest paging and wireless messaging company, today announced the voluntary redemption of 1,797,103 shares of its 15% cumulative series A preferred stock (series A preferred), on a pro-rata basis from all holders, constituting approximately 30% of the share class outstanding. Redemption notice was previously sent to the holders of record on August 29, 2003. The redemption price of $11.13 per share was funded with $20.0 million of cash balances generated from operations. After the redemption Metrocall had approximately 4.12 million shares of its series A preferred outstanding with an aggregate liquidation preference of approximately $46.7 million.

     During 2003, Metrocall has repaid or redeemed an aggregate $101.5 million face amount, or approximately 68.5%, of its debt and preferred stock obligations.

     Additionally today, Metrocall also paid a cash dividend on the series A preferred of $0.4208 per share, or approximately $2.5 million in the aggregate, for holders of record on September 15, 2003, which represented dividends that accrued on the series A preferred from July 1, 2003 through September 30, 2003.

About Metrocall, Inc.

     Metrocall, Inc., headquartered in Alexandria, Virginia, is the nation’s second largest narrowband wireless messaging provider offering paging products and other wireless services to business and individual subscribers. With national networks and operations, the Company provides reliable and cost effective wireless services that are well suited for solving the mobile business communication needs. Metrocall focuses on the business-to-business marketplace and supports organizations of all sizes, with a special emphasis on the medical and government sectors. In addition to traditional numeric and one-way text paging, the Company also offers two-way interactive advanced messaging, 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 and campus environments. 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. Business Risks include the possibility that two-way service may lack vendor support, quantity and quality. 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.