<PAGE>
 
     As filed with the Securities and Exchange Commission on May 27, 1998.

                                                      Registration No. 333-_____
================================================================================
                       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
Incorporation or Organization)                         Identification Number)


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

                          SKYTEL COMMUNICATIONS, INC.
                   1998 OUTSIDE DIRECTORS' STOCK OPTION 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           POWELL, GOLDSTEIN, FRAZER & MURPHY LLP
     COUNSEL 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...............................        250,000(2)             $24.41           $6,102,500.00             $1,800.24
--------------------------------------------------------------------------------------------------------------------------------
Common Stock, par value
$.01 per share...............................        305,000(3)             $24.41           $7,445,050.00             $2,196.29
--------------------------------------------------------------------------------------------------------------------------------
</TABLE>
(1)  In addition, this Registration Statement also covers such indeterminable
     number of additional shares as may become issuable to prevent dilution in
     the event of stock splits, stock dividends or similar transactions pursuant
     to the terms of the SkyTel Communications, Inc. 1998 Outside Directors'
     Stock Option Plan (the "Plan").
(2)  Representing shares to be issued by SkyTel Communications, Inc. (the
     "Company") in connection with the Plan.
(3)  Representing shares to be issued by the Company in connection with certain
     individual non-plan stock options.
(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").
<PAGE>
 
                                     PART I

              INFORMATION REQUIRED IN THE SECTION 10(a) PROSPECTUS


    The document(s) containing the information specified in this Part I will be
sent or given to the Plan participants as specified by Rule 428(b)(1) of the
Securities Act.

                                      I-1
<PAGE>
 
                                    PART II

               INFORMATION REQUIRED IN THE REGISTRATION STATEMENT


ITEM 3.  INCORPORATION OF DOCUMENTS BY REFERENCE.

    The following documents filed with the Securities and Exchange Commission
(the "Commission") are incorporated herein by reference:


    (1)  The Company's Current Report on Form 8-K dated May 27, 1998 (File 
         No. 0-17316);

    (2)  The Company's Quarterly Report on Form 10-Q for the quarterly period
         ended March 31, 1998 (File No. 0-17316);

    (3)  The Company's Annual Report on Form 10-K for the fiscal year ended
         December 31, 1997 (File No. 0-17316);

    (4)  The description of the Company's common stock, par value $.01 per share
         (the "Common Stock"), contained in the Company's Registration Statement
         on Form 10, filed on November 18, 1988 and declared effective on
         December 9, 1988 (File No. 0-17316);

    (5)  The amended description of the Company's Common Stock contained in the
         Form 8 Amendment to the Registration Statement on Form 10, filed on
         April 4, 1989 (File No. 0-17316); and

    (6)  The description of the Company's Rights to Purchase Stock contained in
         the Registration Statement on Form 8-A, filed on August 3, 1989 (File
         No. 0-17316).

    All documents subsequently filed by the Company pursuant to Sections 13(a),
13(c), 14 and 15(d) of the Securities Exchange Act of 1934, as amended, prior to
the filing of a post-effective amendment which indicates that all securities
offered have been sold or which deregisters all securities then remaining
unsold, shall be deemed to be incorporated by reference in this Registration
Statement and to be a part thereof from the date of filing of such documents.

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.

                                      II-1
<PAGE>
 
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
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.

                                      II-2
<PAGE>
 
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 Commission copies of
all such omitted promissory notes, conditional sales contracts and other
instruments and agreements as the Commission requests.

<TABLE>
<CAPTION>
EXHIBIT NO.       DESCRIPTION
---------------   -----------
<S>               <C> 
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).
</TABLE> 

                                      II-3
<PAGE>
 
<TABLE>
<CAPTION>
EXHIBIT NO.       DESCRIPTION
-----------       -----------
<S>               <C> 
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).
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).
</TABLE> 

                                      II-4
<PAGE>
 
<TABLE>
<CAPTION>
EXHIBIT NO.       DESCRIPTION
-----------       -----------
<S>               <C> 
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.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).
</TABLE> 

                                      II-5
<PAGE>
 
<TABLE>
<CAPTION>
EXHIBIT NO.       DESCRIPTION
-----------       -----------
<S>               <C> 
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).
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.
</TABLE> 

                                      II-6
<PAGE>
 
<TABLE>
<CAPTION>
EXHIBIT NO.       DESCRIPTION
-----------       -----------
<S>               <C> 
23.1*             Consent of Arthur Andersen LLP.
24.1              Power of Attorney (Included in the signature page in Part II of
                  this Registration Statement).
99.1*             Form of Stock Option Agreement by and between the Company and each
                  of certain optionees (including a schedule of parties to the stock
                  option agreement).
</TABLE>


______________
*Filed herewith


ITEM 9.  UNDERTAKINGS.

         (a)  The undersigned Registrant hereby undertakes:

              (1)  To file, during any period in which offers or sales are being
made, a post-effective amendment to this registration statement:

                          (i)    To include any prospectus required by Section
              10(a)(3) of the Securities Act of 1933;

                          (ii)   To reflect in the prospectus any facts or
              events arising after the effective date of the registration
              statement (or the most recent post-effective amendment thereof)
              which, individually or in the aggregate, represent a fundamental
              change in the information set forth in the registration statement;
              and

                          (iii)  To include any material information with
              respect to the plan of distribution not previously disclosed in
              the registration statement or any material change to such
              information in the registration statement.

       Provided, however, that paragraphs (a)(1)(i) and (a)(1)(ii) do not apply
if the registration statement is on Form S-3, Form S-8 or Form F-3, and the
information required to be included in a post-effective amendment by those
paragraphs is contained in periodic reports filed with or furnished to the
Commission by the Registrant pursuant to Section 13 or 15(d) of the Securities
Exchange Act of 1934 that are incorporated by reference in the registration
statement.

              (2)  That, for the purpose of determining any liability under the
Securities Act of 1933, each such post-effective amendment shall be deemed to be
a new registration statement relating to the securities offered therein, and the
offering of such securities at that time shall be deemed to be the initial bona
fide offering thereof.

              (3)  To remove from registration by means of a post-effective
amendment any of the securities being registered which remain unsold at the
termination of the offering.

                                      II-7
<PAGE>
 
     (b)  The undersigned Registrant hereby undertakes that, for purposes of
determining any liability under the Securities Act of 1933, each filing of the
Registrant's annual report pursuant to Section 13(a) or Section 15(d) of the
Securities Exchange Act of 1934 (and, where applicable, each filing of an
employee benefit plan's annual report pursuant to Section 15(d) of the
Securities Exchange Act of 1934) that is incorporated by reference in the
registration statement shall be deemed to be a new registration statement
relating to the securities offered therein, and the offering of such securities
at the time shall be deemed to be the initial bona fide offering thereof.

     (c)  Insofar as indemnification for liabilities arising under the
Securities Act of 1933 may be permitted to directors, officers and controlling
persons of the Registrant pursuant to the foregoing provisions, or otherwise,
the Registrant has been advised that in the opinion of the Securities and
Exchange Commission such indemnification is against public policy as expressed
in the Act and is, therefore, unenforceable. In the event that a claim for
indemnification against such liabilities (other than the payment by the
Registrant of expenses incurred or paid by a director, officer or controlling
person of the Registrant in the successful defense of any action, suit or
proceeding) is asserted by such director, officer or controlling person in
connection with the securities being registered, the Registrant will, unless in
the opinion of its counsel the matter has been settled by controlling precedent,
submit to a court of appropriate jurisdiction the question whether such
indemnification by it is against public policy as expressed in the Act and will
be governed by the final adjudication of such issue.

                                      II-8
<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 27th day
of 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.

                                      II-9
<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 27, 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 

                                     II-10
<PAGE>
 
                                 EXHIBIT INDEX
                                 -------------
                                        
<TABLE>
<CAPTION>
EXHIBIT NO.       DESCRIPTION
-----------       -----------
<S>               <C> 
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).
</TABLE> 

                                     II-11
<PAGE>
 
<TABLE>
<CAPTION>
EXHIBIT NO.       DESCRIPTION
-----------       -----------
<S>               <C> 
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).
</TABLE> 

                                     II-12
<PAGE>
 
<TABLE>
<CAPTION>
EXHIBIT NO.       DESCRIPTION
-----------       -----------
<S>               <C> 
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).
</TABLE> 

                                     II-13
<PAGE>
 
<TABLE>
<CAPTION>
EXHIBIT NO.       DESCRIPTION
-----------       -----------
<S>               <C> 
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 in Part II of
                  this Registration Statement).
99.1*             Form of Stock Option Agreement by and between the Company and each
                  of certain optionees (including a schedule of parties to the stock
                  option agreement).
</TABLE>
______________
*Filed herewith

                                     II-14
[{"type": "S-8", "sequence": "1", "description": "FORM S-8", "secsgml_size_bytes": 44614}]
{"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-53733", "film-number": "98632491"}, "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-_____
================================================================================
                       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
Incorporation or Organization)                         Identification Number)

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

                          SKYTEL COMMUNICATIONS, INC.
                   1998 OUTSIDE DIRECTORS' STOCK OPTION 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           POWELL, GOLDSTEIN, FRAZER & MURPHY LLP
     COUNSEL 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...............................        250,000(2)             $24.41           $6,102,500.00             $1,800.24
--------------------------------------------------------------------------------------------------------------------------------
Common Stock, par value
$.01 per share...............................        305,000(3)             $24.41           $7,445,050.00             $2,196.29
--------------------------------------------------------------------------------------------------------------------------------
(1)  In addition, this Registration Statement also covers such indeterminable
     number of additional shares as may become issuable to prevent dilution in
     the event of stock splits, stock dividends or similar transactions pursuant
     to the terms of the SkyTel Communications, Inc. 1998 Outside Directors'
     Stock Option Plan (the "Plan").
(2)  Representing shares to be issued by SkyTel Communications, Inc. (the
     "Company") in connection with the Plan.
(3)  Representing shares to be issued by the Company in connection with certain
     individual non-plan stock options.
(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").
PART I

              INFORMATION REQUIRED IN THE SECTION 10(a) PROSPECTUS

    The document(s) containing the information specified in this Part I will be
sent or given to the Plan participants as specified by Rule 428(b)(1) of the
Securities Act.

                                      I-1
PART II

               INFORMATION REQUIRED IN THE REGISTRATION STATEMENT

ITEM 3.  INCORPORATION OF DOCUMENTS BY REFERENCE.

    The following documents filed with the Securities and Exchange Commission
(the "Commission") are incorporated herein by reference:

    (1)  The Company's Current Report on Form 8-K dated May 27, 1998 (File 
         No. 0-17316);

    (2)  The Company's Quarterly Report on Form 10-Q for the quarterly period
         ended March 31, 1998 (File No. 0-17316);

    (3)  The Company's Annual Report on Form 10-K for the fiscal year ended
         December 31, 1997 (File No. 0-17316);

    (4)  The description of the Company's common stock, par value $.01 per share
         (the "Common Stock"), contained in the Company's Registration Statement
         on Form 10, filed on November 18, 1988 and declared effective on
         December 9, 1988 (File No. 0-17316);

    (5)  The amended description of the Company's Common Stock contained in the
         Form 8 Amendment to the Registration Statement on Form 10, filed on
         April 4, 1989 (File No. 0-17316); and

    (6)  The description of the Company's Rights to Purchase Stock contained in
         the Registration Statement on Form 8-A, filed on August 3, 1989 (File
         No. 0-17316).

    All documents subsequently filed by the Company pursuant to Sections 13(a),
13(c), 14 and 15(d) of the Securities Exchange Act of 1934, as amended, prior to
the filing of a post-effective amendment which indicates that all securities
offered have been sold or which deregisters all securities then remaining
unsold, shall be deemed to be incorporated by reference in this Registration
Statement and to be a part thereof from the date of filing of such documents.

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.

                                      II-1
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
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.

                                      II-2
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 Commission copies of
all such omitted promissory notes, conditional sales contracts and other
instruments and agreements as the Commission requests.
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).
II-3
EXHIBIT NO.       DESCRIPTION
-----------       -----------
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).
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).
II-4
EXHIBIT NO.       DESCRIPTION
-----------       -----------
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.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).
II-5
EXHIBIT NO.       DESCRIPTION
-----------       -----------
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).
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.
II-6
EXHIBIT NO.       DESCRIPTION
-----------       -----------
23.1*             Consent of Arthur Andersen LLP.
24.1              Power of Attorney (Included in the signature page in Part II of
                  this Registration Statement).
99.1*             Form of Stock Option Agreement by and between the Company and each
                  of certain optionees (including a schedule of parties to the stock
                  option agreement).
______________
*Filed herewith

ITEM 9.  UNDERTAKINGS.

         (a)  The undersigned Registrant hereby undertakes:

              (1)  To file, during any period in which offers or sales are being
made, a post-effective amendment to this registration statement:

                          (i)    To include any prospectus required by Section
              10(a)(3) of the Securities Act of 1933;

                          (ii)   To reflect in the prospectus any facts or
              events arising after the effective date of the registration
              statement (or the most recent post-effective amendment thereof)
              which, individually or in the aggregate, represent a fundamental
              change in the information set forth in the registration statement;
              and

                          (iii)  To include any material information with
              respect to the plan of distribution not previously disclosed in
              the registration statement or any material change to such
              information in the registration statement.

       Provided, however, that paragraphs (a)(1)(i) and (a)(1)(ii) do not apply
if the registration statement is on Form S-3, Form S-8 or Form F-3, and the
information required to be included in a post-effective amendment by those
paragraphs is contained in periodic reports filed with or furnished to the
Commission by the Registrant pursuant to Section 13 or 15(d) of the Securities
Exchange Act of 1934 that are incorporated by reference in the registration
statement.

              (2)  That, for the purpose of determining any liability under the
Securities Act of 1933, each such post-effective amendment shall be deemed to be
a new registration statement relating to the securities offered therein, and the
offering of such securities at that time shall be deemed to be the initial bona
fide offering thereof.

              (3)  To remove from registration by means of a post-effective
amendment any of the securities being registered which remain unsold at the
termination of the offering.

                                      II-7
(b)  The undersigned Registrant hereby undertakes that, for purposes of
determining any liability under the Securities Act of 1933, each filing of the
Registrant's annual report pursuant to Section 13(a) or Section 15(d) of the
Securities Exchange Act of 1934 (and, where applicable, each filing of an
employee benefit plan's annual report pursuant to Section 15(d) of the
Securities Exchange Act of 1934) that is incorporated by reference in the
registration statement shall be deemed to be a new registration statement
relating to the securities offered therein, and the offering of such securities
at the time shall be deemed to be the initial bona fide offering thereof.

     (c)  Insofar as indemnification for liabilities arising under the
Securities Act of 1933 may be permitted to directors, officers and controlling
persons of the Registrant pursuant to the foregoing provisions, or otherwise,
the Registrant has been advised that in the opinion of the Securities and
Exchange Commission such indemnification is against public policy as expressed
in the Act and is, therefore, unenforceable. In the event that a claim for
indemnification against such liabilities (other than the payment by the
Registrant of expenses incurred or paid by a director, officer or controlling
person of the Registrant in the successful defense of any action, suit or
proceeding) is asserted by such director, officer or controlling person in
connection with the securities being registered, the Registrant will, unless in
the opinion of its counsel the matter has been settled by controlling precedent,
submit to a court of appropriate jurisdiction the question whether such
indemnification by it is against public policy as expressed in the Act and will
be governed by the final adjudication of such issue.

                                      II-8
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 27th day
of 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.

                                      II-9
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 27, 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 

                                     II-10
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).
II-11
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).
II-12
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).
II-13
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 in Part II of
                  this Registration Statement).
99.1*             Form of Stock Option Agreement by and between the Company and each
                  of certain optionees (including a schedule of parties to the stock
                  option agreement).
______________
*Filed herewith

                                     II-14