For Immediate Release:
Tuesday, September 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

Dividend also to be Paid September 30

     Alexandria, VA, Tuesday, September 2, 2003 - Metrocall Holdings, Inc. (OTCBB: MTOH), the second largest paging and wireless messaging carrier in the United States, today announced that on August 29, 2003, it had mailed notices of redemption to holders of record, as of August 28, of its 15% cumulative series A preferred stock (series A preferred) issued in connection with its October 2002 reorganization. On September 30, 2003, Metrocall will redeem, on a pro-rata basis from all holders, shares representing in the aggregate approximately 30% of the entire share class outstanding. Approximately 1,797,103 shares will be redeemed by the Company at a redemption amount of approximately $11.13 per share. This voluntary redemption of shares with an aggregate liquidation preference of $20.0 million will be completed using cash balances generated from operations. After the redemption, Metrocall will have approximately 4.12 million shares of its series A preferred outstanding with an aggregate liquidation preference of approximately $46.7 million. The payment follows the retirement in full of approximately $81.5 million aggregate principal amount of Metrocall’s long-term debt securities through June 30, 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.

     Additionally Metrocall’s board of directors declared a cash dividend on the series A preferred of $0.4208 per share for holders of record on September 15, 2003. This dividend will be paid out on September 30, 2003 and represents dividends that accrued on the preferred stock from July 1, 2003 through September 30, 2003.

     “These developments demonstrate Metrocall’s commitment to satisfying the remaining obligations of the Company’s 2002 Plan of Reorganization significantly ahead of schedule,” said Vincent D. Kelly, Metrocall President & CEO. “So far in 2003 Metrocall has become the only major independent wireless messaging company to become debt free by retiring our entire $81.5 million debt portfolio and has announced our intention to retire $20 million on September 30^th of our outstanding series A preferred stock, representing 30% of the class. These events were made possible due to our unmatched record of six straight sequential quarters of free cash flow growth, the best revenue retention statistics in the industry and among the highest free cash flow margins in our sector. While the company and industry still face many challenges and an eroding revenue environment, our customers, employees, and shareholders can be proud of our track record of creating value and strong operating performance.”

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.