<PAGE>
 
     As filed with the Securities and Exchange Commission on May 27, 1998.
                                                      Registration No. 333-42494
--------------------------------------------------------------------------------

                       SECURITIES AND EXCHANGE COMMISSION
                              Washington, DC 20549

                                    FORM S-8
                             REGISTRATION STATEMENT
                                     UNDER
                           THE SECURITIES ACT OF 1933
                                        
                          SKYTEL COMMUNICATIONS, INC.
             (Exact Name of Registrant as Specified in Its Charter)

                  DELAWARE                              64-0518209
(State or Other Jurisdiction of          (I.R.S. Employer Identification Number)
Incorporation or Organization)  

                             200 SOUTH LAMAR STREET
                          MTEL CENTRE, SOUTH BUILDING
                           JACKSON MISSISSIPPI 39201
              (Address of Principal Executive Offices) (Zip Code)

                          SKYTEL COMMUNICATIONS, INC.
                    SECTION 401 (k) EMPLOYEE RETIREMENT PLAN
                            (Full Title of the Plan)

                                        
                             LEONARD G. KRISS, ESQ.
              SENIOR VICE PRESIDENT, GENERAL COUNSEL AND SECRETARY
                          SKYTEL COMMUNICATIONS, INC.
                             200 SOUTH LAMAR STREET
                          MTEL CENTRE, SOUTH BUILDING
                          JACKSON, MISSISSIPPI  39201
                    (Name and Address of Agent for Service)

                                 (601) 944-1300
         (Telephone Number, Including Area Code, of Agent for Service)


                          COPIES OF COMMUNICATIONS TO:


         LEONARD G. KRISS, ESQ.                LINZY O. SCOTT III, ESQ.
SENIOR VICE PRESIDENT, GENERAL COUNSEL   POWELL, GOLDSTEIN, FRAZER & MURPHY LLP
            AND SECRETARY                          SIXTEENTH FLOOR           
      SKYTEL COMMUNICATIONS, INC.             191 PEACHTREE STREET, N.E. 
        200 SOUTH LAMAR STREET                 ATLANTA, GEORGIA  30303    
      MTEL CENTRE, SOUTH BUILDING          
      JACKSON, MISSISSIPPI  39201

                        CALCULATION OF REGISTRATION FEE

<TABLE>
<CAPTION>
-----------------------------------------------------------------------------------------------------------------
                                                    Proposed Maximum       Proposed Maximum
      Title of Securities          Amount to Be      Offering Price       Aggregate Offering        Amount of
      To Be Registered(1)           Registered        Per Share(4)             Price(4)          Registration Fee
-----------------------------------------------------------------------------------------------------------------
<S>                                <C>             <C>                   <C>                     <C>
Common Stock, par value
$.01 per share..................     500,000 (2)             $24.41             $12,205,000             $3,600.48
-----------------------------------------------------------------------------------------------------------------
Common Stock, par value
$.01 per share..................     500,000 (3)             $24.41             $12,205,000             $3,600.48
-----------------------------------------------------------------------------------------------------------------
</TABLE>

(1)  In addition, this Registration Statement also covers an indeterminate
     amount of interests to be offered or sold pursuant to the SkyTel
     Communications, Inc. Section 401(k) Employee Retirement Plan (the "Plan").
(2)  Representing shares to be issued that, at the option of SkyTel
     Communications, Inc. (the "Company"), may be used pursuant to any matching
     contributions in connection with the Plan.
(3)  Representing shares that may be acquired by the Trustee of the Plan and
     held for the account of Plan participants.
(4)  Estimated solely for purposes of calculating the registration fee pursuant
     to Rule 457(h)(1) under the Securities Act of 1933, as amended (the
     "Securities Act").

As required by the General Instruction to Item E for the use of Form S-8 of the
Securities Act, this registration of additional shares under the Plan
incorporates by reference the original filing on Form S-8 of the Plan (File No.
033-42494).
<PAGE>
 
ITEM 6.  INDEMNIFICATION OF DIRECTORS AND OFFICERS.

    Set forth below is a description of certain provisions of the Company's
Restated Certificate of Incorporation, as amended (the "Certificate of
Incorporation"), the Company's Bylaws, as amended (the "Bylaws"), and the
General Corporation Law of the State of Delaware ("DGCL"), as such provisions
relate to the indemnification of the directors and officers of the Company.
This description is intended only as a summary and is qualified in its entirety
by reference to the Certificate of Incorporation, the Bylaws and the DGCL.

Elimination of Liability in Certain Circumstances

    The Certificate of Incorporation provides that to the full extent permitted
by the DGCL or any other applicable law presently or hereafter in effect, no
director of the Company shall be personally liable to the Company or its
stockholders for or with respect to any acts or omissions in the performance of
his or her duties as a director of the Company.  The DGCL provides that a
corporation may limit or eliminate a director's personal liability for monetary
damages to the corporation or its stockholders, except for liability for (i) any
breach of the director's duty of loyalty to such corporation or its
stockholders, (ii) acts or omissions not in good faith or which involve
intentional misconduct or a knowing violation of law, (iii) paying a dividend or
approving a stock repurchase in violation of Section 174 of the DGCL, or (iv)
any transaction from which the director derived an improper personal benefit.

    While Article TENTH of the Certificate of Incorporation provides directors
with protection from awards for monetary damages for breaches of the duty of
care, it does not eliminate the director's duty of care.  Accordingly, the
Certificate of Incorporation will have no effect on the availability of
equitable remedies such as an injunction or recision based on a director's
breach of the duty of care.  The provisions of Article TENTH as described above
apply to officers of the Company only if they are directors of the Company and
are acting in their capacity as directors, and does not apply to officers of the
Company who are not directors.

Indemnification and Insurance

    Under the DGCL, directors and officers as well as other employees and
individuals may be indemnified against expenses (including attorneys' fees),
judgments, fines and amounts paid in settlement in connection with specified
actions, suits or proceedings whether civil, criminal, administrative or
investigative (other than an action by or in the right of the corporation as a
derivative action) if they acted in good faith and in a manner they reasonably
believed to be in or not opposed to the best interest of the corporation, and
with respect to any criminal action or proceeding, had no reasonable cause to
believe their conduct was unlawful.

    Under the DGCL, directors and officers as well as other employees and
individuals may be indemnified against expenses (including attorneys' fees)
incurred in connection with specified actions, suits or proceedings, by or in
the right of the corporation if they acted in good faith and in a manner they
reasonably believed to be in or not opposed to the best interests of the
corporation and except that no indemnification may be made in respect of any

                                       1
<PAGE>
 
claim, issue or matter as to which such person shall have been adjudged to be
liable to the corporation unless and only to the extent that the Delaware Court
of Chancery or the court in which such action or suit was brought shall
determine upon application that, despite the adjudication of liability but in
view of all the circumstances of the case, such person is fairly and reasonably
entitled to indemnity for such expenses which the Delaware Court of Chancery or
such other court shall deem proper.

    Article NINTH of the Certificate of Incorporation provides to directors and
officers indemnification to the full extent permitted from time to time by the
DGCL or any other applicable law as presently or hereafter in effect, thereby
affording the directors and officers of the Company the protection available to
directors and officers of Delaware corporations.  Article NINTH of the
Certificate of Incorporation also authorizes the Company to enter into one or
more agreements with any person which provide for indemnification greater or
different than that provided in Article NINTH.

    Pursuant to Delaware law, the Company may purchase and maintain insurance on
behalf of any person who is or was a director, officer, employee or agent of the
Company, or is or was serving at the request of the Company as a director,
officer, employee or agent of another corporation, partnership, joint venture,
trust or other enterprise against any liability asserted against him and
incurred by him in any such capacity, or arising out of his status as such,
whether or not the Company would have the power to indemnify him against such
liability under the applicable sections of the DGCL.  The Company has such an
insurance policy.

ITEM 8.  EXHIBITS.

    The following items are filed as exhibits to this Registration Statement.
Where such filing is made by incorporation by reference to a previously filed
statement or report, such statement or report is identified in parentheses.
There are omitted from the exhibits filed with this Registration Statement
certain promissory notes, conditional sales contracts and other instruments and
agreements with respect to long-term debt of the Company, none of which
authorizes securities in a total amount that exceeds 10% of the total assets of
the Company on a consolidated basis.  Pursuant to Item 601(b)(4)(iii) of
Regulation S-K, the Company hereby agrees to file with the Securities and
Exchange Commission copies of all such omitted promissory notes, conditional
sales contracts and other instruments and agreements as the Commission requests.
In addition, the Company undertakes to submit the Plan, as amended, to the 
Internal Revenue Service ("IRS") in a timely manner and will make all changes 
required by the IRS in order to qualify the Plan.

Exhibit No.       Description
-----------       ----------- 
4.1               Restated Certificate of Incorporation of the Company
                  (Incorporated by reference to Exhibit 3.3 to the Registration
                  Statement on Form 10 filed on November 18, 1988 and effective
                  on December 29, 1988).

4.2               Bylaws of the Company, as amended (Incorporated by reference
                  to Exhibit 3.4 to the Registration Statement on Form 10 of the
                  Company filed on November 18, 1988 and effective on December
                  29, 1988).


                                       2
<PAGE>
 
Exhibit No.       Description
-----------       ----------- 
4.3               Certificate of Designations of Series C Junior Participating
                  Preferred Stock of the Company (Incorporated by reference to
                  Exhibit 3 to the Registration Statement on Form 8-A of the
                  Company filed on August 3, 1989).

4.4               Rights Agreement dated as of July 26, 1989 between the Company
                  and NCNB Texas National Bank (Incorporated by reference to
                  Exhibit 2 to the Registration Statement on Form 8-A of the
                  Company filed on August 3, 1989).

4.5               Form of Right Certificate of the Company (Incorporated by
                  reference to Exhibit 1 to the Registration Statement on Form 
                  8-A of the Company filed on August 3, 1989).

4.6               Indenture dated as of May 28, 1992 between the Company and
                  NationsBank of Texas, N.A., as Trustee, relating to the
                  Company's 6.75% Convertible Subordinated Debentures due May
                  15, 2002, including as an exhibit thereto the form of
                  Debenture (Incorporated by reference to Exhibit 4.3 and 28 to
                  the Company's Quarterly Report on Form 10-Q for the quarter
                  ended September 30, 1992).

4.7               Form of Indenture between the Company and Texas Commerce Bank
                  National Association, as Trustee, relating to the 13.5% Senior
                  Notes due 2002, including as an exhibit thereto the form of
                  the Note (Incorporated by reference to Exhibit 4.8 to the
                  Company's Registration Statement on Form S-3 filed on November
                  10, 1994 and effective on December 21, 1994).

4.8               Certificate of Designations of the $2.25 Cumulative
                  Convertible Exchangeable Preferred Stock of the Company
                  (Incorporated by reference to Exhibit 4.1 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended September
                  30, 1993).

4.9               Credit, Security, Guaranty and Pledge Agreement dated as of
                  December 21, 1995 by and among the Company, the lenders
                  referred to therein, Chemical Bank, Credit Lyonnais New York
                  Branch and J.P. Morgan Securities, Inc. (Incorporated by
                  reference to Exhibit 4.7 to the Company's Annual Report on
                  Form 10-K for the year ended December 31, 1995).

                                       3
<PAGE>
 
Exhibit No.       Description
-----------       ----------- 
4.10              Contribution Agreement of the Company dated as of December 21,
                  1995 entered into in connection with the Credit, Security,
                  Guaranty and Pledge Agreement dated as of December 21, 1995 by
                  and among the Company, the lenders referred to therein,
                  Chemical Bank, Credit Lyonnais New York Branch and J.P. Morgan
                  Securities, Inc. (Incorporated by reference to Exhibit 4.8 to
                  the Company's Annual Report on Form 10-K for the year ended
                  December 31, 1995).

4.11              Patent and Security Agreement of the Company dated as of
                  December 21, 1995 entered into in connection with the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995 by and among the Company, the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.9 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1995).

4.12              Trademark Security Agreement of the Company dated as of
                  December 21, 1995 entered into in connection with the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21,1995 by and among the Company, the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.10 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1995).

4.13              Copyright Security Agreement of the Company dated as of
                  December 21, 1995 entered into in connection with the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995 by and among the Company, the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.11 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1995).

4.14              Subordination Agreement dated as of December 21, 1995 by and
                  among the Company and Chemical Bank (Incorporated by reference
                  to Exhibit 4.12 to the Company's Annual Report on Form 10-K
                  for the year ended December 31, 1995).

4.15              Amendment No. 1 dated as of March 27, 1996 to the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995 by and among the Company, the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.13 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1995).

                                       4
<PAGE>
 
Exhibit No.       Description
-----------       ----------- 
4.16              Certificate of Designation relating to the Series A 7.5%
                  Cumulative Convertible Accruing Pay-In-Kind Preferred Stock
                  (Incorporated by reference to Exhibit 4.1 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended March 31,
                  1996).

4.17              Certificate of Designation relating to the Series B 7.5%
                  Cumulative Convertible Accruing Pay-In-Kind Preferred Stock
                  (Incorporated by reference to Exhibit 4.2 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended March 31,
                  1996).

4.18              Certificate of Designation relating to the series C 7.5%
                  Cumulative Convertible Accruing Pay-In-Kind Preferred Stock
                  (Incorporated by reference to Exhibit 4.3 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended March 31,
                  1996).

4.19              Supplemental Indenture dated as of July 18, 1996 between the
                  Company and Texas Commerce Bank National Association, as
                  Trustee, relating to the 13.5% Senior Notes due 2002
                  (Incorporated by reference to Exhibit 4.2 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended June 30,
                  1996).

4.20              Amendment No. 2 dated as of August 23, 1996 to the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995, as amended, by and among the Company, the lenders
                  referred to therein, Chemical Bank, Credit Lyonnais New York
                  Branch and J.P. Morgan Securities, Inc. (Incorporated by
                  reference to Exhibit 4.1 to the Company's Quarterly Report on
                  Form 10-Q for the year ended September 30, 1996).

4.21              Amendment No. 3 dated as of March 26, 1997 to the Credit,
                  Security, Guarantee and Pledge Agreement dated as of December
                  21, 1995, as amended, by and among the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.19 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1996).

4.22              Certificate of Amendment of Restated Certificate of
                  Incorporation dated May 30, 1996 (Incorporated by reference to
                  Exhibit 4.20 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1996).

                                       5
<PAGE>
 
Exhibit No.       Description
-----------       ----------- 
4.23              Amendment No. 4 dated as of October 8, 1997 to the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995, as amended, by and among the Company, the lenders
                  referred to therein, Chase Manhattan Bank, Credit Lyonnais,
                  New York Branch and J.P. Morgan Securities, Inc. (Incorporated
                  by reference to Exhibit 4.1 to the Company's Quarterly Report
                  on Form 10-Q for the quarter ended September 30, 1997).

4.24*             SkyTel Communications, Inc. Section 401(k) Employee Retirement
                  Plan.

4.25*             Trust Agreement by and between Merrill Lynch Trust Company of
                  America and the Company dated as of February 2, 1998.

4.26*             Certificate of Amendment of the Restated Certificate of
                  Incorporation dated May 21, 1998.

4.27*             Specimen Stock Certificate of the Company.

5.1*              Opinion of Powell, Goldstein, Frazer & Murphy LLP.          
                                                                              
23.1*             Consent of Arthur Andersen LLP.
                                                                              
24.1              Power of Attorney (Included in the signature page of this
                  Registration Statement).


______________
*Filed herewith

                                       6
<PAGE>
 
                                   SIGNATURES
                                        

         Pursuant to the requirements of the Securities Act of 1933, the
Registrant 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, hereunto
duly authorized, in the City of Jackson, State of Mississippi, on this 27 May,
1998.

                                    SKYTEL COMMUNICATIONS, INC.


                                    By: /s/ John T. Stupka
                                        -------------------------------------
                                        John T. Stupka
                                        President and Chief Executive Officer



                               POWER OF ATTORNEY
                               -----------------
                                        
          KNOW ALL MEN BY THESE PRESENTS, that each person whose signature
appears below constitutes and appoints Leonard G. Kriss and Robert Kaiser, and
each of them, his true and lawful attorneys-in-fact and agents, with full power
of substitution and resubstitution, for him and in his name, place and stead, in
any and all capacities to sign any or all amendments to this Registration
Statement, and to file the same, with all exhibits thereto and other documents
in connection therewith, with the Securities and Exchange Commission, granting
unto each of said attorneys-in-fact and agents full power and authority to do
and perform each and every act and thing requisite and necessary to be done in
and about the premises, as fully as to all intents and purposes as he might or
could do in person, hereby ratifying and confirming all that each of said
attorneys-in-fact and agents, or his substitute or substitutes, may lawfully do
or cause to be done by virtue hereof.

                                       7
<PAGE>
 
          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
          ---------                 -----                 ----

/s/ John T. Stupka         President, Chief Executive      May 21, 1998
------------------------      Officer and Director
John T. Stupka             (Principal Executive Officer)
                  
                 
/s/ Robert Kaiser         Senior Vice President--Finance   May 21, 1998
------------------------    and Chief Financial Officer
Robert Kaiser                (Principal Financial and
                                Accounting Officer)
                  
/s/ Haley Barbour                   Director               May 21, 1998
------------------------
Haley Barbour     
                 
/s/ Thomas G. Barksdale             Director               May 21, 1998
------------------------
Thomas G. Barksdale                                                     
                                                                      
/s/ Jai P. Bhagat                   Director               May 21, 1998
------------------------
Jai P. Bhagat                                                         
                                                                      
                                    Director               May __, 1998
------------------------
Gregory B. Maffei 
                 
/s/ John N. Palmer            Chairman of the Board        May 27, 1998
------------------------
John N. Palmer    
                 
/s/ R. Faser Triplett               Director               May 21, 1998
------------------------
R. Faser Triplett                                                      
                                                                       
/s/ R. Gerald Turner                 Director              May 21, 1998
------------------------
R. Gerald Turner                                                       
                                                                       
                                     Director              May __, 1998
------------------------
E. Lee Walker                                                          

/s/ John E. Welsh III                Director              May 21, 1998 
------------------------
John E. Welsh III  

                                       8
<PAGE>
 
  Pursuant to the requirements of the Securities Act of 1933, the trustees (or
other persons who administer the Plan) have duly caused this Registration
Statement to be signed on its behalf by the undersigned, thereunto duly
authorized, in the City of Jackson, State of Mississippi, on May 27, 1998.

                            SKYTEL COMMUNICATIONS, INC. SECTION 
                            401(k) EMPLOYEE RETIREMENT PLAN

                            By:  SKYTEL COMMUNICATIONS, INC.,
                                 AS PLAN ADMINISTRATOR

                            By:       /s/ Leonard G. Kriss
                                      ---------------------------------------
                            Name:     Leonard G. Kriss
                                      ---------------------------------------
                            Title:    Senior Vice President & General Counsel
                                      ---------------------------------------
 

                                       9
<PAGE>
 
                                  EXHIBIT INDEX
                                 --------------
                                        
EXHIBIT NO.       Description
----------        -----------
4.1               Restated Certificate of Incorporation of the Company
                  (Incorporated by reference to Exhibit 3.3 to the Registration
                  Statement on Form 10 filed on November 18, 1988 and effective
                  on December 29, 1988).

4.2               Bylaws of the Company, as amended (Incorporated by reference
                  to Exhibit 3.4 to the Registration Statement on Form 10 of the
                  Company filed on November 18, 1988 and effective on December
                  29, 1988).

4.3               Certificate of Designations of Series C Junior Participating
                  Preferred Stock of the Company (Incorporated by reference to
                  Exhibit 3 to the Registration Statement on Form 8-A of the
                  Company filed on August 3, 1989).

4.4               Rights Agreement dated as of July 26, 1989 between the Company
                  and NCNB Texas National Bank (Incorporated by reference to
                  Exhibit 2 to the Registration Statement on Form 8-A of the
                  Company filed on August 3, 1989).

4.5               Form of Right Certificate of the Company (Incorporated by
                  reference to Exhibit 1 to the Registration Statement on Form 
                  8-A of the Company filed on August 3, 1989).

4.6               Indenture dated as of May 28, 1992 between the Company and
                  NationsBank of Texas, N.A., as Trustee, relating to the
                  Company's 6.75% Convertible Subordinated Debentures due May
                  15, 2002, including as an exhibit thereto the form of
                  Debenture (Incorporated by reference to Exhibit 4.3 and 28 to
                  the Company's Quarterly Report on Form 10-Q for the quarter
                  ended September 30, 1992).

4.7               Form of Indenture between the Company and Texas Commerce Bank
                  National Association, as Trustee, relating to the 13.5% Senior
                  Notes due 2002, including as an exhibit thereto the form of
                  the Note (Incorporated by reference to Exhibit 4.8 to the
                  Company's Registration Statement on Form S-3 filed on November
                  10, 1994 and effective on December 21, 1994).

4.8               Certificate of Designations of the $2.25 Cumulative
                  Convertible Exchangeable Preferred Stock of the Company
                  (Incorporated by reference to Exhibit 4.1 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended September
                  30, 1993).

                                       10
<PAGE>
 
EXHIBIT NO.       Description
----------        -----------
4.9               Credit, Security, Guaranty and Pledge Agreement dated as of
                  December 21, 1995 by and among the Company, the lenders
                  referred to therein, Chemical Bank, Credit Lyonnais New York
                  Branch and J.P. Morgan Securities, Inc. (Incorporated by
                  reference to Exhibit 4.7 to the Company's Annual Report on
                  Form 10-K for the year ended December 31, 1995).

4.10              Contribution Agreement of the Company dated as of December 21,
                  1995 entered into in connection with the Credit, Security,
                  Guaranty and Pledge Agreement dated as of December 21, 1995 by
                  and among the Company, the lenders referred to therein,
                  Chemical Bank, Credit Lyonnais New York Branch and J.P. Morgan
                  Securities, Inc. (Incorporated by reference to Exhibit 4.8 to
                  the Company's Annual Report on Form 10-K for the year ended
                  December 31, 1995).

4.11              Patent and Security Agreement of the Company dated as of
                  December 21, 1995 entered into in connection with the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995 by and among the Company, the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.9 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1995).

4.12              Trademark Security Agreement of the Company dated as of
                  December 21, 1995 entered into in connection with the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21,1995 by and among the Company, the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.10 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1995).

4.13              Copyright Security Agreement of the Company dated as of
                  December 21, 1995 entered into in connection with the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995 by and among the Company, the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.11 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1995).

4.14              Subordination Agreement dated as of December 21, 1995 by and
                  among the Company and Chemical Bank (Incorporated by reference
                  to Exhibit 4.12 to the Company's Annual Report on Form 10-K
                  for the year ended December 31, 1995).

                                       11
<PAGE>
 
EXHIBIT NO.       Description
----------        -----------
4.15              Amendment No. 1 dated as of March 27, 1996 to the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995 by and among the Company, the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.13 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1995).

4.16              Certificate of Designation relating to the Series A 7.5%
                  Cumulative Convertible Accruing Pay-In-Kind Preferred Stock
                  (Incorporated by reference to Exhibit 4.1 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended March 31,
                  1996).

4.17              Certificate of Designation relating to the Series B 7.5%
                  Cumulative Convertible Accruing Pay-In-Kind Preferred Stock
                  (Incorporated by reference to Exhibit 4.2 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended March 31,
                  1996).

4.18              Certificate of Designation relating to the series C 7.5%
                  Cumulative Convertible Accruing Pay-In-Kind Preferred Stock
                  (Incorporated by reference to Exhibit 4.3 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended March 31,
                  1996).

4.19              Supplemental Indenture dated as of July 18, 1996 between the
                  Company and Texas Commerce Bank National Association, as
                  Trustee, relating to the 13.5% Senior Notes due 2002
                  (Incorporated by reference to Exhibit 4.2 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended June 30,
                  1996.
                  
4.20              Amendment No. 2 dated as of August 23, 1996 to the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995, as amended, by and among the Company, the lenders
                  referred to therein, Chemical Bank, Credit Lyonnais New York
                  Branch and J.P. Morgan Securities, Inc. (Incorporated by
                  reference to Exhibit 4.1 to the Company's Quarterly Report on
                  Form 10-Q for the year ended September 30, 1996).

4.21              Amendment No. 3 dated as of March 26, 1997 to the Credit,
                  Security, Guarantee and Pledge Agreement dated as of December
                  21, 1995, as amended, by and among the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.19 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1996).

                                       12
<PAGE>
 
EXHIBIT NO.       Description
----------        -----------
4.22              Certificate of Amendment of Restated Certificate of
                  Incorporation dated May 30, 1996 (Incorporated by reference to
                  Exhibit 4.20 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1996).

4.23              Amendment No. 4 dated as of October 8, 1997 to the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995, as amended, by and among the Company, the lenders
                  referred to therein, Chase Manhattan Bank, Credit Lyonnais,
                  New York Branch and J.P. Morgan Securities, Inc. (Incorporated
                  by reference to Exhibit 4.1 to the Company's Quarterly Report
                  on Form 10-Q for the quarter ended September 30, 1997).

4.24*             SkyTel Communications, Inc. Section 401(k) Employee Retirement
                  Plan.

4.25*             Trust Agreement by and between Merrill Lynch Trust Company of
                  America and the Company dated as of February 2, 1998.

4.26*             Certificate of Amendment of the Restated Certificate of
                  Incorporation dated May 21, 1998.

4.27*             Specimen Stock Certificate of the Company.

5.1*              Opinion of Powell, Goldstein, Frazer & Murphy LLP.

23.1*             Consent of Arthur Andersen LLP.

24.1              Power of Attorney (Included in the signature page of this
                  Registration Statement).


______________
*Filed herewith

                                       13
[{"type": "S-8", "sequence": "1", "description": "FORM S-8", "secsgml_size_bytes": 38202}]
{"company-data": {"conformed-name": "SKYTEL COMMUNICATIONS INC", "cik": "0000842915", "assigned-sic": "4812", "irs-number": "640518209", "state-of-incorporation": "DE", "fiscal-year-end": "1231"}, "filing-values": {"form-type": "S-8", "act": "33", "file-number": "333-53727", "film-number": "98632483"}, "business-address": {"street1": "200 S LAMAR ST", "street2": "SECURITY CENTRE S BUILDING", "city": "JACKSON", "state": "MS", "zip": "39201", "phone": "6019441300"}, "mail-address": {"street1": "200 S LAMAR ST", "street2": "SECURITY CENTRE SOUTH BUILDING", "city": "JACKSON", "state": "MS", "zip": "39201"}, "former-company": {"former-conformed-name": "MOBILE TELECOMMUNICATION TECHNOLOGIES CORP", "date-changed": "19920703"}}
As filed with the Securities and Exchange Commission on May 27, 1998.
                                                      Registration No. 333-42494
--------------------------------------------------------------------------------

                       SECURITIES AND EXCHANGE COMMISSION
                              Washington, DC 20549

                                    FORM S-8
                             REGISTRATION STATEMENT
                                     UNDER
                           THE SECURITIES ACT OF 1933
                                        
                          SKYTEL COMMUNICATIONS, INC.
             (Exact Name of Registrant as Specified in Its Charter)

                  DELAWARE                              64-0518209
(State or Other Jurisdiction of          (I.R.S. Employer Identification Number)
Incorporation or Organization)  

                             200 SOUTH LAMAR STREET
                          MTEL CENTRE, SOUTH BUILDING
                           JACKSON MISSISSIPPI 39201
              (Address of Principal Executive Offices) (Zip Code)

                          SKYTEL COMMUNICATIONS, INC.
                    SECTION 401 (k) EMPLOYEE RETIREMENT PLAN
                            (Full Title of the Plan)

                                        
                             LEONARD G. KRISS, ESQ.
              SENIOR VICE PRESIDENT, GENERAL COUNSEL AND SECRETARY
                          SKYTEL COMMUNICATIONS, INC.
                             200 SOUTH LAMAR STREET
                          MTEL CENTRE, SOUTH BUILDING
                          JACKSON, MISSISSIPPI  39201
                    (Name and Address of Agent for Service)

                                 (601) 944-1300
         (Telephone Number, Including Area Code, of Agent for Service)

                          COPIES OF COMMUNICATIONS TO:

         LEONARD G. KRISS, ESQ.                LINZY O. SCOTT III, ESQ.
SENIOR VICE PRESIDENT, GENERAL COUNSEL   POWELL, GOLDSTEIN, FRAZER & MURPHY LLP
            AND SECRETARY                          SIXTEENTH FLOOR           
      SKYTEL COMMUNICATIONS, INC.             191 PEACHTREE STREET, N.E. 
        200 SOUTH LAMAR STREET                 ATLANTA, GEORGIA  30303    
      MTEL CENTRE, SOUTH BUILDING          
      JACKSON, MISSISSIPPI  39201

                        CALCULATION OF REGISTRATION FEE
-----------------------------------------------------------------------------------------------------------------
                                                    Proposed Maximum       Proposed Maximum
      Title of Securities          Amount to Be      Offering Price       Aggregate Offering        Amount of
      To Be Registered(1)           Registered        Per Share(4)             Price(4)          Registration Fee
-----------------------------------------------------------------------------------------------------------------
Common Stock, par value
$.01 per share..................     500,000 (2)             $24.41             $12,205,000             $3,600.48
-----------------------------------------------------------------------------------------------------------------
Common Stock, par value
$.01 per share..................     500,000 (3)             $24.41             $12,205,000             $3,600.48
-----------------------------------------------------------------------------------------------------------------
(1)  In addition, this Registration Statement also covers an indeterminate
     amount of interests to be offered or sold pursuant to the SkyTel
     Communications, Inc. Section 401(k) Employee Retirement Plan (the "Plan").
(2)  Representing shares to be issued that, at the option of SkyTel
     Communications, Inc. (the "Company"), may be used pursuant to any matching
     contributions in connection with the Plan.
(3)  Representing shares that may be acquired by the Trustee of the Plan and
     held for the account of Plan participants.
(4)  Estimated solely for purposes of calculating the registration fee pursuant
     to Rule 457(h)(1) under the Securities Act of 1933, as amended (the
     "Securities Act").

As required by the General Instruction to Item E for the use of Form S-8 of the
Securities Act, this registration of additional shares under the Plan
incorporates by reference the original filing on Form S-8 of the Plan (File No.
033-42494).
ITEM 6.  INDEMNIFICATION OF DIRECTORS AND OFFICERS.

    Set forth below is a description of certain provisions of the Company's
Restated Certificate of Incorporation, as amended (the "Certificate of
Incorporation"), the Company's Bylaws, as amended (the "Bylaws"), and the
General Corporation Law of the State of Delaware ("DGCL"), as such provisions
relate to the indemnification of the directors and officers of the Company.
This description is intended only as a summary and is qualified in its entirety
by reference to the Certificate of Incorporation, the Bylaws and the DGCL.

Elimination of Liability in Certain Circumstances

    The Certificate of Incorporation provides that to the full extent permitted
by the DGCL or any other applicable law presently or hereafter in effect, no
director of the Company shall be personally liable to the Company or its
stockholders for or with respect to any acts or omissions in the performance of
his or her duties as a director of the Company.  The DGCL provides that a
corporation may limit or eliminate a director's personal liability for monetary
damages to the corporation or its stockholders, except for liability for (i) any
breach of the director's duty of loyalty to such corporation or its
stockholders, (ii) acts or omissions not in good faith or which involve
intentional misconduct or a knowing violation of law, (iii) paying a dividend or
approving a stock repurchase in violation of Section 174 of the DGCL, or (iv)
any transaction from which the director derived an improper personal benefit.

    While Article TENTH of the Certificate of Incorporation provides directors
with protection from awards for monetary damages for breaches of the duty of
care, it does not eliminate the director's duty of care.  Accordingly, the
Certificate of Incorporation will have no effect on the availability of
equitable remedies such as an injunction or recision based on a director's
breach of the duty of care.  The provisions of Article TENTH as described above
apply to officers of the Company only if they are directors of the Company and
are acting in their capacity as directors, and does not apply to officers of the
Company who are not directors.

Indemnification and Insurance

    Under the DGCL, directors and officers as well as other employees and
individuals may be indemnified against expenses (including attorneys' fees),
judgments, fines and amounts paid in settlement in connection with specified
actions, suits or proceedings whether civil, criminal, administrative or
investigative (other than an action by or in the right of the corporation as a
derivative action) if they acted in good faith and in a manner they reasonably
believed to be in or not opposed to the best interest of the corporation, and
with respect to any criminal action or proceeding, had no reasonable cause to
believe their conduct was unlawful.

    Under the DGCL, directors and officers as well as other employees and
individuals may be indemnified against expenses (including attorneys' fees)
incurred in connection with specified actions, suits or proceedings, by or in
the right of the corporation if they acted in good faith and in a manner they
reasonably believed to be in or not opposed to the best interests of the
corporation and except that no indemnification may be made in respect of any

                                       1
claim, issue or matter as to which such person shall have been adjudged to be
liable to the corporation unless and only to the extent that the Delaware Court
of Chancery or the court in which such action or suit was brought shall
determine upon application that, despite the adjudication of liability but in
view of all the circumstances of the case, such person is fairly and reasonably
entitled to indemnity for such expenses which the Delaware Court of Chancery or
such other court shall deem proper.

    Article NINTH of the Certificate of Incorporation provides to directors and
officers indemnification to the full extent permitted from time to time by the
DGCL or any other applicable law as presently or hereafter in effect, thereby
affording the directors and officers of the Company the protection available to
directors and officers of Delaware corporations.  Article NINTH of the
Certificate of Incorporation also authorizes the Company to enter into one or
more agreements with any person which provide for indemnification greater or
different than that provided in Article NINTH.

    Pursuant to Delaware law, the Company may purchase and maintain insurance on
behalf of any person who is or was a director, officer, employee or agent of the
Company, or is or was serving at the request of the Company as a director,
officer, employee or agent of another corporation, partnership, joint venture,
trust or other enterprise against any liability asserted against him and
incurred by him in any such capacity, or arising out of his status as such,
whether or not the Company would have the power to indemnify him against such
liability under the applicable sections of the DGCL.  The Company has such an
insurance policy.

ITEM 8.  EXHIBITS.

    The following items are filed as exhibits to this Registration Statement.
Where such filing is made by incorporation by reference to a previously filed
statement or report, such statement or report is identified in parentheses.
There are omitted from the exhibits filed with this Registration Statement
certain promissory notes, conditional sales contracts and other instruments and
agreements with respect to long-term debt of the Company, none of which
authorizes securities in a total amount that exceeds 10% of the total assets of
the Company on a consolidated basis.  Pursuant to Item 601(b)(4)(iii) of
Regulation S-K, the Company hereby agrees to file with the Securities and
Exchange Commission copies of all such omitted promissory notes, conditional
sales contracts and other instruments and agreements as the Commission requests.
In addition, the Company undertakes to submit the Plan, as amended, to the 
Internal Revenue Service ("IRS") in a timely manner and will make all changes 
required by the IRS in order to qualify the Plan.

Exhibit No.       Description
-----------       ----------- 
4.1               Restated Certificate of Incorporation of the Company
                  (Incorporated by reference to Exhibit 3.3 to the Registration
                  Statement on Form 10 filed on November 18, 1988 and effective
                  on December 29, 1988).

4.2               Bylaws of the Company, as amended (Incorporated by reference
                  to Exhibit 3.4 to the Registration Statement on Form 10 of the
                  Company filed on November 18, 1988 and effective on December
                  29, 1988).

                                       2
Exhibit No.       Description
-----------       ----------- 
4.3               Certificate of Designations of Series C Junior Participating
                  Preferred Stock of the Company (Incorporated by reference to
                  Exhibit 3 to the Registration Statement on Form 8-A of the
                  Company filed on August 3, 1989).

4.4               Rights Agreement dated as of July 26, 1989 between the Company
                  and NCNB Texas National Bank (Incorporated by reference to
                  Exhibit 2 to the Registration Statement on Form 8-A of the
                  Company filed on August 3, 1989).

4.5               Form of Right Certificate of the Company (Incorporated by
                  reference to Exhibit 1 to the Registration Statement on Form 
                  8-A of the Company filed on August 3, 1989).

4.6               Indenture dated as of May 28, 1992 between the Company and
                  NationsBank of Texas, N.A., as Trustee, relating to the
                  Company's 6.75% Convertible Subordinated Debentures due May
                  15, 2002, including as an exhibit thereto the form of
                  Debenture (Incorporated by reference to Exhibit 4.3 and 28 to
                  the Company's Quarterly Report on Form 10-Q for the quarter
                  ended September 30, 1992).

4.7               Form of Indenture between the Company and Texas Commerce Bank
                  National Association, as Trustee, relating to the 13.5% Senior
                  Notes due 2002, including as an exhibit thereto the form of
                  the Note (Incorporated by reference to Exhibit 4.8 to the
                  Company's Registration Statement on Form S-3 filed on November
                  10, 1994 and effective on December 21, 1994).

4.8               Certificate of Designations of the $2.25 Cumulative
                  Convertible Exchangeable Preferred Stock of the Company
                  (Incorporated by reference to Exhibit 4.1 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended September
                  30, 1993).

4.9               Credit, Security, Guaranty and Pledge Agreement dated as of
                  December 21, 1995 by and among the Company, the lenders
                  referred to therein, Chemical Bank, Credit Lyonnais New York
                  Branch and J.P. Morgan Securities, Inc. (Incorporated by
                  reference to Exhibit 4.7 to the Company's Annual Report on
                  Form 10-K for the year ended December 31, 1995).

                                       3
Exhibit No.       Description
-----------       ----------- 
4.10              Contribution Agreement of the Company dated as of December 21,
                  1995 entered into in connection with the Credit, Security,
                  Guaranty and Pledge Agreement dated as of December 21, 1995 by
                  and among the Company, the lenders referred to therein,
                  Chemical Bank, Credit Lyonnais New York Branch and J.P. Morgan
                  Securities, Inc. (Incorporated by reference to Exhibit 4.8 to
                  the Company's Annual Report on Form 10-K for the year ended
                  December 31, 1995).

4.11              Patent and Security Agreement of the Company dated as of
                  December 21, 1995 entered into in connection with the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995 by and among the Company, the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.9 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1995).

4.12              Trademark Security Agreement of the Company dated as of
                  December 21, 1995 entered into in connection with the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21,1995 by and among the Company, the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.10 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1995).

4.13              Copyright Security Agreement of the Company dated as of
                  December 21, 1995 entered into in connection with the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995 by and among the Company, the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.11 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1995).

4.14              Subordination Agreement dated as of December 21, 1995 by and
                  among the Company and Chemical Bank (Incorporated by reference
                  to Exhibit 4.12 to the Company's Annual Report on Form 10-K
                  for the year ended December 31, 1995).

4.15              Amendment No. 1 dated as of March 27, 1996 to the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995 by and among the Company, the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.13 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1995).

                                       4
Exhibit No.       Description
-----------       ----------- 
4.16              Certificate of Designation relating to the Series A 7.5%
                  Cumulative Convertible Accruing Pay-In-Kind Preferred Stock
                  (Incorporated by reference to Exhibit 4.1 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended March 31,
                  1996).

4.17              Certificate of Designation relating to the Series B 7.5%
                  Cumulative Convertible Accruing Pay-In-Kind Preferred Stock
                  (Incorporated by reference to Exhibit 4.2 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended March 31,
                  1996).

4.18              Certificate of Designation relating to the series C 7.5%
                  Cumulative Convertible Accruing Pay-In-Kind Preferred Stock
                  (Incorporated by reference to Exhibit 4.3 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended March 31,
                  1996).

4.19              Supplemental Indenture dated as of July 18, 1996 between the
                  Company and Texas Commerce Bank National Association, as
                  Trustee, relating to the 13.5% Senior Notes due 2002
                  (Incorporated by reference to Exhibit 4.2 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended June 30,
                  1996).

4.20              Amendment No. 2 dated as of August 23, 1996 to the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995, as amended, by and among the Company, the lenders
                  referred to therein, Chemical Bank, Credit Lyonnais New York
                  Branch and J.P. Morgan Securities, Inc. (Incorporated by
                  reference to Exhibit 4.1 to the Company's Quarterly Report on
                  Form 10-Q for the year ended September 30, 1996).

4.21              Amendment No. 3 dated as of March 26, 1997 to the Credit,
                  Security, Guarantee and Pledge Agreement dated as of December
                  21, 1995, as amended, by and among the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.19 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1996).

4.22              Certificate of Amendment of Restated Certificate of
                  Incorporation dated May 30, 1996 (Incorporated by reference to
                  Exhibit 4.20 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1996).

                                       5
Exhibit No.       Description
-----------       ----------- 
4.23              Amendment No. 4 dated as of October 8, 1997 to the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995, as amended, by and among the Company, the lenders
                  referred to therein, Chase Manhattan Bank, Credit Lyonnais,
                  New York Branch and J.P. Morgan Securities, Inc. (Incorporated
                  by reference to Exhibit 4.1 to the Company's Quarterly Report
                  on Form 10-Q for the quarter ended September 30, 1997).

4.24*             SkyTel Communications, Inc. Section 401(k) Employee Retirement
                  Plan.

4.25*             Trust Agreement by and between Merrill Lynch Trust Company of
                  America and the Company dated as of February 2, 1998.

4.26*             Certificate of Amendment of the Restated Certificate of
                  Incorporation dated May 21, 1998.

4.27*             Specimen Stock Certificate of the Company.

5.1*              Opinion of Powell, Goldstein, Frazer & Murphy LLP.          
                                                                              
23.1*             Consent of Arthur Andersen LLP.
                                                                              
24.1              Power of Attorney (Included in the signature page of this
                  Registration Statement).

______________
*Filed herewith

                                       6
SIGNATURES
                                        

         Pursuant to the requirements of the Securities Act of 1933, the
Registrant 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, hereunto
duly authorized, in the City of Jackson, State of Mississippi, on this 27 May,
1998.

                                    SKYTEL COMMUNICATIONS, INC.

                                    By: /s/ John T. Stupka
                                        -------------------------------------
                                        John T. Stupka
                                        President and Chief Executive Officer

                               POWER OF ATTORNEY
                               -----------------
                                        
          KNOW ALL MEN BY THESE PRESENTS, that each person whose signature
appears below constitutes and appoints Leonard G. Kriss and Robert Kaiser, and
each of them, his true and lawful attorneys-in-fact and agents, with full power
of substitution and resubstitution, for him and in his name, place and stead, in
any and all capacities to sign any or all amendments to this Registration
Statement, and to file the same, with all exhibits thereto and other documents
in connection therewith, with the Securities and Exchange Commission, granting
unto each of said attorneys-in-fact and agents full power and authority to do
and perform each and every act and thing requisite and necessary to be done in
and about the premises, as fully as to all intents and purposes as he might or
could do in person, hereby ratifying and confirming all that each of said
attorneys-in-fact and agents, or his substitute or substitutes, may lawfully do
or cause to be done by virtue hereof.

                                       7
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
          ---------                 -----                 ----

/s/ John T. Stupka         President, Chief Executive      May 21, 1998
------------------------      Officer and Director
John T. Stupka             (Principal Executive Officer)
                  
                 
/s/ Robert Kaiser         Senior Vice President--Finance   May 21, 1998
------------------------    and Chief Financial Officer
Robert Kaiser                (Principal Financial and
                                Accounting Officer)
                  
/s/ Haley Barbour                   Director               May 21, 1998
------------------------
Haley Barbour     
                 
/s/ Thomas G. Barksdale             Director               May 21, 1998
------------------------
Thomas G. Barksdale                                                     
                                                                      
/s/ Jai P. Bhagat                   Director               May 21, 1998
------------------------
Jai P. Bhagat                                                         
                                                                      
                                    Director               May __, 1998
------------------------
Gregory B. Maffei 
                 
/s/ John N. Palmer            Chairman of the Board        May 27, 1998
------------------------
John N. Palmer    
                 
/s/ R. Faser Triplett               Director               May 21, 1998
------------------------
R. Faser Triplett                                                      
                                                                       
/s/ R. Gerald Turner                 Director              May 21, 1998
------------------------
R. Gerald Turner                                                       
                                                                       
                                     Director              May __, 1998
------------------------
E. Lee Walker                                                          

/s/ John E. Welsh III                Director              May 21, 1998 
------------------------
John E. Welsh III  

                                       8
Pursuant to the requirements of the Securities Act of 1933, the trustees (or
other persons who administer the Plan) have duly caused this Registration
Statement to be signed on its behalf by the undersigned, thereunto duly
authorized, in the City of Jackson, State of Mississippi, on May 27, 1998.

                            SKYTEL COMMUNICATIONS, INC. SECTION 
                            401(k) EMPLOYEE RETIREMENT PLAN

                            By:  SKYTEL COMMUNICATIONS, INC.,
                                 AS PLAN ADMINISTRATOR

                            By:       /s/ Leonard G. Kriss
                                      ---------------------------------------
                            Name:     Leonard G. Kriss
                                      ---------------------------------------
                            Title:    Senior Vice President & General Counsel
                                      ---------------------------------------
 

                                       9
EXHIBIT INDEX
                                 --------------
                                        
EXHIBIT NO.       Description
----------        -----------
4.1               Restated Certificate of Incorporation of the Company
                  (Incorporated by reference to Exhibit 3.3 to the Registration
                  Statement on Form 10 filed on November 18, 1988 and effective
                  on December 29, 1988).

4.2               Bylaws of the Company, as amended (Incorporated by reference
                  to Exhibit 3.4 to the Registration Statement on Form 10 of the
                  Company filed on November 18, 1988 and effective on December
                  29, 1988).

4.3               Certificate of Designations of Series C Junior Participating
                  Preferred Stock of the Company (Incorporated by reference to
                  Exhibit 3 to the Registration Statement on Form 8-A of the
                  Company filed on August 3, 1989).

4.4               Rights Agreement dated as of July 26, 1989 between the Company
                  and NCNB Texas National Bank (Incorporated by reference to
                  Exhibit 2 to the Registration Statement on Form 8-A of the
                  Company filed on August 3, 1989).

4.5               Form of Right Certificate of the Company (Incorporated by
                  reference to Exhibit 1 to the Registration Statement on Form 
                  8-A of the Company filed on August 3, 1989).

4.6               Indenture dated as of May 28, 1992 between the Company and
                  NationsBank of Texas, N.A., as Trustee, relating to the
                  Company's 6.75% Convertible Subordinated Debentures due May
                  15, 2002, including as an exhibit thereto the form of
                  Debenture (Incorporated by reference to Exhibit 4.3 and 28 to
                  the Company's Quarterly Report on Form 10-Q for the quarter
                  ended September 30, 1992).

4.7               Form of Indenture between the Company and Texas Commerce Bank
                  National Association, as Trustee, relating to the 13.5% Senior
                  Notes due 2002, including as an exhibit thereto the form of
                  the Note (Incorporated by reference to Exhibit 4.8 to the
                  Company's Registration Statement on Form S-3 filed on November
                  10, 1994 and effective on December 21, 1994).

4.8               Certificate of Designations of the $2.25 Cumulative
                  Convertible Exchangeable Preferred Stock of the Company
                  (Incorporated by reference to Exhibit 4.1 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended September
                  30, 1993).

                                       10
EXHIBIT NO.       Description
----------        -----------
4.9               Credit, Security, Guaranty and Pledge Agreement dated as of
                  December 21, 1995 by and among the Company, the lenders
                  referred to therein, Chemical Bank, Credit Lyonnais New York
                  Branch and J.P. Morgan Securities, Inc. (Incorporated by
                  reference to Exhibit 4.7 to the Company's Annual Report on
                  Form 10-K for the year ended December 31, 1995).

4.10              Contribution Agreement of the Company dated as of December 21,
                  1995 entered into in connection with the Credit, Security,
                  Guaranty and Pledge Agreement dated as of December 21, 1995 by
                  and among the Company, the lenders referred to therein,
                  Chemical Bank, Credit Lyonnais New York Branch and J.P. Morgan
                  Securities, Inc. (Incorporated by reference to Exhibit 4.8 to
                  the Company's Annual Report on Form 10-K for the year ended
                  December 31, 1995).

4.11              Patent and Security Agreement of the Company dated as of
                  December 21, 1995 entered into in connection with the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995 by and among the Company, the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.9 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1995).

4.12              Trademark Security Agreement of the Company dated as of
                  December 21, 1995 entered into in connection with the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21,1995 by and among the Company, the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.10 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1995).

4.13              Copyright Security Agreement of the Company dated as of
                  December 21, 1995 entered into in connection with the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995 by and among the Company, the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.11 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1995).

4.14              Subordination Agreement dated as of December 21, 1995 by and
                  among the Company and Chemical Bank (Incorporated by reference
                  to Exhibit 4.12 to the Company's Annual Report on Form 10-K
                  for the year ended December 31, 1995).

                                       11
EXHIBIT NO.       Description
----------        -----------
4.15              Amendment No. 1 dated as of March 27, 1996 to the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995 by and among the Company, the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.13 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1995).

4.16              Certificate of Designation relating to the Series A 7.5%
                  Cumulative Convertible Accruing Pay-In-Kind Preferred Stock
                  (Incorporated by reference to Exhibit 4.1 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended March 31,
                  1996).

4.17              Certificate of Designation relating to the Series B 7.5%
                  Cumulative Convertible Accruing Pay-In-Kind Preferred Stock
                  (Incorporated by reference to Exhibit 4.2 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended March 31,
                  1996).

4.18              Certificate of Designation relating to the series C 7.5%
                  Cumulative Convertible Accruing Pay-In-Kind Preferred Stock
                  (Incorporated by reference to Exhibit 4.3 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended March 31,
                  1996).

4.19              Supplemental Indenture dated as of July 18, 1996 between the
                  Company and Texas Commerce Bank National Association, as
                  Trustee, relating to the 13.5% Senior Notes due 2002
                  (Incorporated by reference to Exhibit 4.2 to the Company's
                  Quarterly Report on Form 10-Q for the quarter ended June 30,
                  1996.
                  
4.20              Amendment No. 2 dated as of August 23, 1996 to the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995, as amended, by and among the Company, the lenders
                  referred to therein, Chemical Bank, Credit Lyonnais New York
                  Branch and J.P. Morgan Securities, Inc. (Incorporated by
                  reference to Exhibit 4.1 to the Company's Quarterly Report on
                  Form 10-Q for the year ended September 30, 1996).

4.21              Amendment No. 3 dated as of March 26, 1997 to the Credit,
                  Security, Guarantee and Pledge Agreement dated as of December
                  21, 1995, as amended, by and among the lenders referred to
                  therein, Chemical Bank, Credit Lyonnais New York Branch and
                  J.P. Morgan Securities, Inc. (Incorporated by reference to
                  Exhibit 4.19 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1996).

                                       12
EXHIBIT NO.       Description
----------        -----------
4.22              Certificate of Amendment of Restated Certificate of
                  Incorporation dated May 30, 1996 (Incorporated by reference to
                  Exhibit 4.20 to the Company's Annual Report on Form 10-K for
                  the year ended December 31, 1996).

4.23              Amendment No. 4 dated as of October 8, 1997 to the Credit,
                  Security, Guaranty and Pledge Agreement dated as of December
                  21, 1995, as amended, by and among the Company, the lenders
                  referred to therein, Chase Manhattan Bank, Credit Lyonnais,
                  New York Branch and J.P. Morgan Securities, Inc. (Incorporated
                  by reference to Exhibit 4.1 to the Company's Quarterly Report
                  on Form 10-Q for the quarter ended September 30, 1997).

4.24*             SkyTel Communications, Inc. Section 401(k) Employee Retirement
                  Plan.

4.25*             Trust Agreement by and between Merrill Lynch Trust Company of
                  America and the Company dated as of February 2, 1998.

4.26*             Certificate of Amendment of the Restated Certificate of
                  Incorporation dated May 21, 1998.

4.27*             Specimen Stock Certificate of the Company.

5.1*              Opinion of Powell, Goldstein, Frazer & Murphy LLP.

23.1*             Consent of Arthur Andersen LLP.

24.1              Power of Attorney (Included in the signature page of this
                  Registration Statement).

______________
*Filed herewith

                                       13