1

                                                                    EXHIBIT 23.1

                        CONSENT OF INDEPENDENT AUDITORS

     We consent to the reference to our firm under the caption "Experts" and to
the use of our reports dated May 3, 2000, with respect to the consolidated
financial statements and financial statement schedule of Paging Network, Inc. as
of December 31, 1998 and 1999, and for each of the three years in the period
ended December 31, 1999, in the Registration Statement (Form S-4) and related
Prospectus of Paging Network, Inc. for the registration of 616,830,757 shares of
Paging Network, Inc. common stock and 13,780,000 shares of Class B common stock
of Vast Solutions, Inc., a wholly-owned subsidiary of Paging Network, Inc., to
be exchanged for all of the outstanding 8.875% senior subordinated notes due
2006, 10.125% senior subordinated notes due 2007, and 10% senior subordinated
notes due 2008 of Paging Network, Inc. (the Registration Statement).


     We also consent to the use of our report dated February 12, 1999, except
for the eighth paragraph of Note 1 and the second paragraph of Note 6, as to
which the date is March 26, 1999, and the ninth paragraph of Note 1, as to which
the date is April 12, 1999, with respect to the financial statements of
MobileMedia Communications, Inc. as of December 31, 1997 and 1998, and for each
of the three years in the period ended December 31, 1998, in the Registration
Statement.


                                                 /s/ ERNST & YOUNG LLP
                                          --------------------------------------

Dallas, Texas

July 7, 2000