<PAGE>   1
--------------------------------------------------------------------------------
As filed with the Securities and Exchange Commission on January 27, 1999
                                                 Registration No. 333__________

                       SECURITIES AND EXCHANGE COMMISSION
                             WASHINGTON, D.C. 20549
                                    FORM S-8
                             REGISTRATION STATEMENT
                                      under
                           THE SECURITIES ACT OF 1933

                             ----------------------


                                 METROCALL, INC.
             (Exact name of registrant as specified in its charter)

           DELAWARE                                       54-1215634
(State or other jurisdiction of                        (I.R.S. employer
incorporation or organization)                      identification number)

                              6677 Richmond Highway
                           Alexandria, Virginia 22306
                                 (703) 660-6677
                    (Address of Principal Executive Offices)

                                 METROCALL, INC.
                      AMENDED EMPLOYEE STOCK PURCHASE PLAN
                            (Full title of the plan)

                             WILLIAM L. COLLINS, III
                             CHIEF EXECUTIVE OFFICER
                              6677 RICHMOND HIGHWAY
                           ALEXANDRIA, VIRGINIA 22306
                                 (703) 660-6677

   (Name and address, including zip code, and telephone number, including area
                           code, of agent for service)

                             ----------------------


                                 With a copy to:
                             GEORGE P. STAMAS, ESQ.
                               ROGER J. PATTERSON, ESQ.
                           WILMER, CUTLER & PICKERING
                               2445 M STREET, N.W.
                             WASHINGTON, D.C. 20037
                                 (202) 663-6000

                             ----------------------


                         CALCULATION OF REGISTRATION FEE

<TABLE>
<CAPTION>
----------------------------------------------------------------------------------------------------
                                                              Proposed      Proposed
                             Title of                         Maximum        Maximum
                            Securities          Amount        Offering      Aggregate    Amount of
                              to be             to be          Price        Offering   Registration
     Name of Plan           Registered        Registered     Per Share        Price         Fee
----------------------------------------------------------------------------------------------------
<S>                    <C>                     <C>            <C>         <C>             <C>     
Amended Employee       Common Stock, par       700,000       $5.1875(1)    $3,631,250     $1,010 
Stock Purchase Plan    value $0.01 per
                       share,                  
----------------------------------------------------------------------------------------------------
</TABLE>


(1)    In accordance with Rule 457(h) and Rule 457(c) the aggregate offering
       price and the amount of the registration fee are computed on the basis of
       the average of the high and low prices reported in the Nasdaq Stock
       Market on January 22, 1999.


================================================================================



<PAGE>   2







        Except as set forth below, the entire contents of the Form S-8 filed by
Metrocall, Inc. (the "Company") on November 17, 1995, Registration Statement No.
33-99556, is hereby incorporated by reference.

                                     PART II

ITEM 5. INTERESTS OF NAMED EXPERTS AND COUNSEL

        The legal validity of the Shares of Class A Common Stock of the Company
offered by the Registrant pursuant to this Registration Statement is being
passed upon by Wilmer, Cutler & Pickering.

ITEM 8. EXHIBITS

        The Exhibits to this Registration Statement are listed in the Index to
the Exhibits of this Registration Statement, which Index is herein incorporated
by reference.

            [THE REMAINDER OF THIS PAGE IS INTENTIONALLY LEFT BLANK.]




                                      - 2 -


<PAGE>   3



                                   SIGNATURES

        Pursuant to the requirements of the Securities Act of 1933, the Company
certifies that it has reasonable grounds to believe that it meets all of the
requirements for filing on Form S-8 and has duly caused this registration
statement to be signed on its behalf by the undersigned, thereunto duly
authorized, in Alexandria, Virginia on the 27th day of January, 1999.

                             METROCALL, Inc.

                             By:/s/ VINCENT D. KELLY
                                ------------------------------------------
                                Vincent D. Kelly
                                Chief Financial Officer and Executive Vice
                                President

                                POWER OF ATTORNEY

        Pursuant to the requirements of the Securities Act of 1933, this
Registration Statement has been signed by the following persons in the
capacities and on the dates indicated.

<TABLE>
<CAPTION>
                Signature                              Title                     Date
                ---------                              -----                     ----
<S>                                         <C>                           <C>    

                                            Chairman of the Board          January 27, 1999
                   *
---------------------------------------
           Richard M. Johnston


                                            President, Chief Executive     January 27, 1999
                   *                        Officer and Director
---------------------------------------     (Principal Executive Officer)
         William L. Collins, III            

                                            Chief Financial Officer and
           /s/ VINCENT D. KELLY             Executive Vice President       January 27, 1999
---------------------------------------     (Principal Financial and
             Vincent D. Kelly               Accounting Officer)
                                            

                   *                        Director                       January 27, 1999
---------------------------------------
           Harry L. Brock, Jr.

                   *                        Director                       January 27, 1999
---------------------------------------
             Suzanne S. Brock

                   *                        Director                       January 27, 1999
---------------------------------------
          Francis A. Martin, III
</TABLE>

                                      - 3 -


<PAGE>   4



<TABLE>
<CAPTION>
                Signature                              Title                     Date
                ---------                              -----                     ----
<S>                                         <C>                           <C>    

                  *
---------------------------------------
           Ronald V. Aprahamian              Director                      January 27, 1999

                  *                          
---------------------------------------      Director                      January 27, 1999
            Ray D. Rusenberger

                  *
---------------------------------------
            Elliott H. Singer                Director                      January 27, 1999

                  *
---------------------------------------      Director                      January 27, 1999
              Michael Greene                 

                  *                          
---------------------------------------      Director                      January 27, 1999
             Royce R. Yudkoff

                                                                           January __, 1999
---------------------------------------      Director
             Jackie R. Kimzey

                                                                           January __, 1999
---------------------------------------      Director
           Edward E. Jungerman

                                                                           January __, 1999
---------------------------------------      Director
              Max D. Hopper

*By:       /s/ VINCENT D. KELLY
---------------------------------------
             Vincent D. Kelly
             Attorney-in-Fact
</TABLE>

                                      - 4 -


<PAGE>   5



                                  EXHIBIT INDEX

<TABLE>
<CAPTION>
EXHIBIT
NUMBER      DESCRIPTION
------      -----------

<S>     <C>                                                                        
3.1     Amended and Restated Certificate of Incorporation of Metrocall, Inc., as
        amended (a)

3.3     Seventh Amended and Restated Bylaws of Metrocall, Inc.(b)

4       Amended Employee Stock Purchase Plan (c)

5       Opinion of Wilmer, Cutler & Pickering, as to the legality of the
        securities being registered

23.1    Consent of Arthur Andersen LLP

23.2    Consent of PricewaterhouseCoopers LLP

24      Power of attorney
</TABLE>

-----------

(a)     Incorporated by reference to Metrocall's Registration Statement on Form
        S-4, as amended (File No. 333-44329), filed with the Commission on
        January 15, 1998.

(b)     Incorporated by reference to Metrocall's Report on Form 10-Q for the
        quarter ended June 30, 1998 as filed with the Commission on August 14,
        1998.

(c)     Incorporated by reference to Metrocall's Registration Statement on Form
        S-4 Amendment No. 1 (File No. 333-36079) as filed with the Commission on
        October 27, 1997.

                                      - 5 -
[{"type": "S-8", "sequence": "1", "description": "FORM S-8  RE: AMENDED EMPLOYEE STOCK PURCHASE PLAN", "secsgml_size_bytes": 10229}]
{"company-data": {"conformed-name": "METROCALL INC", "cik": "0000906525", "assigned-sic": "4812", "irs-number": "541215634", "state-of-incorporation": "DE", "fiscal-year-end": "1231"}, "filing-values": {"form-type": "S-8", "act": "33", "file-number": "333-71239", "film-number": "99513701"}, "business-address": {"street1": "6677 RICHMOND HWY", "city": "ALEXANDRIA", "state": "VA", "zip": "22306", "phone": "7036606677"}, "mail-address": {"street1": "6910 RICHMOND HWY", "city": "ALEXANDRIA", "state": "VA", "zip": "22306"}}
1
--------------------------------------------------------------------------------
As filed with the Securities and Exchange Commission on January 27, 1999
                                                 Registration No. 333__________

                       SECURITIES AND EXCHANGE COMMISSION
                             WASHINGTON, D.C. 20549
                                    FORM S-8
                             REGISTRATION STATEMENT
                                      under
                           THE SECURITIES ACT OF 1933

                             ----------------------

                                 METROCALL, INC.
             (Exact name of registrant as specified in its charter)

           DELAWARE                                       54-1215634
(State or other jurisdiction of                        (I.R.S. employer
incorporation or organization)                      identification number)

                              6677 Richmond Highway
                           Alexandria, Virginia 22306
                                 (703) 660-6677
                    (Address of Principal Executive Offices)

                                 METROCALL, INC.
                      AMENDED EMPLOYEE STOCK PURCHASE PLAN
                            (Full title of the plan)

                             WILLIAM L. COLLINS, III
                             CHIEF EXECUTIVE OFFICER
                              6677 RICHMOND HIGHWAY
                           ALEXANDRIA, VIRGINIA 22306
                                 (703) 660-6677

   (Name and address, including zip code, and telephone number, including area
                           code, of agent for service)

                             ----------------------

                                 With a copy to:
                             GEORGE P. STAMAS, ESQ.
                               ROGER J. PATTERSON, ESQ.
                           WILMER, CUTLER & PICKERING
                               2445 M STREET, N.W.
                             WASHINGTON, D.C. 20037
                                 (202) 663-6000

                             ----------------------

                         CALCULATION OF REGISTRATION FEE
----------------------------------------------------------------------------------------------------
                                                              Proposed      Proposed
                             Title of                         Maximum        Maximum
                            Securities          Amount        Offering      Aggregate    Amount of
                              to be             to be          Price        Offering   Registration
     Name of Plan           Registered        Registered     Per Share        Price         Fee
----------------------------------------------------------------------------------------------------
Amended Employee       Common Stock, par       700,000       $5.1875(1)    $3,631,250     $1,010 
Stock Purchase Plan    value $0.01 per
                       share,                  
----------------------------------------------------------------------------------------------------
(1)    In accordance with Rule 457(h) and Rule 457(c) the aggregate offering
       price and the amount of the registration fee are computed on the basis of
       the average of the high and low prices reported in the Nasdaq Stock
       Market on January 22, 1999.

================================================================================
2

        Except as set forth below, the entire contents of the Form S-8 filed by
Metrocall, Inc. (the "Company") on November 17, 1995, Registration Statement No.
33-99556, is hereby incorporated by reference.

                                     PART II

ITEM 5. INTERESTS OF NAMED EXPERTS AND COUNSEL

        The legal validity of the Shares of Class A Common Stock of the Company
offered by the Registrant pursuant to this Registration Statement is being
passed upon by Wilmer, Cutler & Pickering.

ITEM 8. EXHIBITS

        The Exhibits to this Registration Statement are listed in the Index to
the Exhibits of this Registration Statement, which Index is herein incorporated
by reference.

            [THE REMAINDER OF THIS PAGE IS INTENTIONALLY LEFT BLANK.]

                                      - 2 -
3

                                   SIGNATURES

        Pursuant to the requirements of the Securities Act of 1933, the Company
certifies that it has reasonable grounds to believe that it meets all of the
requirements for filing on Form S-8 and has duly caused this registration
statement to be signed on its behalf by the undersigned, thereunto duly
authorized, in Alexandria, Virginia on the 27th day of January, 1999.

                             METROCALL, Inc.

                             By:/s/ VINCENT D. KELLY
                                ------------------------------------------
                                Vincent D. Kelly
                                Chief Financial Officer and Executive Vice
                                President

                                POWER OF ATTORNEY

        Pursuant to the requirements of the Securities Act of 1933, this
Registration Statement has been signed by the following persons in the
capacities and on the dates indicated.
Signature                              Title                     Date
                ---------                              -----                     ----
Chairman of the Board          January 27, 1999
                   *
---------------------------------------
           Richard M. Johnston

                                            President, Chief Executive     January 27, 1999
                   *                        Officer and Director
---------------------------------------     (Principal Executive Officer)
         William L. Collins, III            

                                            Chief Financial Officer and
           /s/ VINCENT D. KELLY             Executive Vice President       January 27, 1999
---------------------------------------     (Principal Financial and
             Vincent D. Kelly               Accounting Officer)
                                            

                   *                        Director                       January 27, 1999
---------------------------------------
           Harry L. Brock, Jr.

                   *                        Director                       January 27, 1999
---------------------------------------
             Suzanne S. Brock

                   *                        Director                       January 27, 1999
---------------------------------------
          Francis A. Martin, III
- 3 -
4
Signature                              Title                     Date
                ---------                              -----                     ----
*
---------------------------------------
           Ronald V. Aprahamian              Director                      January 27, 1999

                  *                          
---------------------------------------      Director                      January 27, 1999
            Ray D. Rusenberger

                  *
---------------------------------------
            Elliott H. Singer                Director                      January 27, 1999

                  *
---------------------------------------      Director                      January 27, 1999
              Michael Greene                 

                  *                          
---------------------------------------      Director                      January 27, 1999
             Royce R. Yudkoff

                                                                           January __, 1999
---------------------------------------      Director
             Jackie R. Kimzey

                                                                           January __, 1999
---------------------------------------      Director
           Edward E. Jungerman

                                                                           January __, 1999
---------------------------------------      Director
              Max D. Hopper

*By:       /s/ VINCENT D. KELLY
---------------------------------------
             Vincent D. Kelly
             Attorney-in-Fact
- 4 -
5

                                  EXHIBIT INDEX
EXHIBIT
NUMBER      DESCRIPTION
------      -----------
3.1     Amended and Restated Certificate of Incorporation of Metrocall, Inc., as
        amended (a)

3.3     Seventh Amended and Restated Bylaws of Metrocall, Inc.(b)

4       Amended Employee Stock Purchase Plan (c)

5       Opinion of Wilmer, Cutler & Pickering, as to the legality of the
        securities being registered

23.1    Consent of Arthur Andersen LLP

23.2    Consent of PricewaterhouseCoopers LLP

24      Power of attorney
-----------

(a)     Incorporated by reference to Metrocall's Registration Statement on Form
        S-4, as amended (File No. 333-44329), filed with the Commission on
        January 15, 1998.

(b)     Incorporated by reference to Metrocall's Report on Form 10-Q for the
        quarter ended June 30, 1998 as filed with the Commission on August 14,
        1998.

(c)     Incorporated by reference to Metrocall's Registration Statement on Form
        S-4 Amendment No. 1 (File No. 333-36079) as filed with the Commission on
        October 27, 1997.

                                      - 5 -