<PAGE>
                                                                     Exhibit 5.1

January 21, 2005

AirGate PCS, Inc.
Harris Tower
233 Peachtree Street NE, Suite 1700
Atlanta, GA 30303

      Re:   AirGate PCS, Inc.
            Registration Statement on Form S-4

Ladies and Gentlemen:

We have acted as counsel to AirGate PCS, Inc., a Delaware corporation (the
"Company") and to the subsidiaries of the Company listed on Schedule 1 hereto
(each, a "Guarantor" and collectively, the "Guarantors"), in connection with the
Registration Statement on Form S-4 (the "Registration Statement") filed by the
Company and the Guarantors with the Securities and Exchange Commission (the
"Commission") under the Securities Act of 1933 (the "Act"). The Registration
Statement relates to the issuance by the Company of up to $175,000,000 aggregate
principal amount of its First Priority Senior Secured Floating Rate Notes due
2011 (the "New Notes") and the issuance by the Guarantors of guarantees (the
"New Guarantees") with respect to the New Notes.

The New Notes and the New Guarantees will be issued under an indenture, dated as
of October 25, 2004 (the "Indenture") among the Company, the Guarantors and The
Bank of New York Trust Company, N. A., as trustee (the "Trustee").

As such counsel and for purposes of our opinions set forth below, we have
examined originals or copies, certified or otherwise identified to our
satisfaction, of such documents, corporate records, certificates of public
officials and other instruments as we have deemed necessary or appropriate as a
basis for the opinions set forth herein, including, without limitation:

            (i)   the Registration Statement;

            (ii)  the Indenture;

            (iii) the New Notes;

            (iv)  the New Guarantees;

            (v)   the certificate of incorporation of the Company and the bylaws
                  of the Company as presently in effect as certified by the
                  Secretary of
<PAGE>
AirGate PCS, Inc.
January 21, 2005
Page 2

                  the Company as of the date hereof (collectively, the "Company
                  Charter Documents");

            (vi)  the certificate of incorporation or corresponding formation
                  document of each of the Guarantors and the bylaws or
                  corresponding governance document of each of the Guarantors as
                  presently in effect as certified by the Secretary of each
                  Guarantor as of the date hereof (collectively, the "Guarantor
                  Charter Documents"; and together with the Company Charter
                  Documents, the "Charter Documents"); and

            (vii) resolutions adopted by the Company's and each Guarantor's
                  board of directors (or equivalent governing body), certified
                  by the respective Secretary of the Company and each such
                  Guarantor, relating to the execution and delivery of, and the
                  performance by the Company and each Guarantor of its
                  respective obligations under, the Transaction Documents (as
                  defined below).

In addition to the foregoing, we have made such investigations of law as we have
deemed necessary or appropriate as a basis for the opinions set forth herein.

The Registration Statement, Registration Rights Agreement, the New Notes, the
New Guarantees and the Indenture are referred to herein, individually, as a
"Transaction Document" and, collectively, as the "Transaction Documents".

In such examination and in rendering the opinions expressed below, we have
assumed: (i) the due authorization, execution and delivery of all agreements,
instruments and other documents by all the parties thereto (other than the due
authorization, execution and delivery of each such agreement, instrument and
document by the Company and the Guarantors); (ii) the genuineness of all
signatures on all documents submitted to us; (iii) the authenticity and
completeness of all documents, corporate records, certificates and other
instruments submitted to us; (iv) that photocopy, electronic, certified,
conformed, facsimile and other copies submitted to us of original documents,
corporate records, certificates and other instruments conform to the original
documents, records, certificates and other instruments, and that all such
original documents were authentic and complete; (v) the legal capacity of all
individuals executing documents; (vi) that the Transaction Documents executed in
connection with the transactions contemplated thereby are the valid and binding
obligations of each of the parties thereto (other than the Company and the
Guarantors), enforceable against such parties (other than the Company and the
Guarantors) in accordance with their respective terms and that no Transaction
Document has been amended or terminated orally or in writing except as has been
disclosed to us; (vii) that the statements contained in the certificates and
comparable documents of public officials, officers and representatives of the
Company and the Guarantors and other persons on which we have relied for the
purposes of this opinion are true and correct; and
<PAGE>
AirGate PCS, Inc.
January 21, 2005
Page 3

(viii) that the rights and remedies set forth in the Transaction Documents will
be exercised reasonably and in good faith and were granted without fraud or
duress and for good, valuable and adequate consideration and without intent to
hinder, delay or defeat any rights of any creditors or stockholders of the
Company or any Guarantor. As to all questions of fact material to this opinion
and as to the materiality of any fact or other matter referred to herein, we
have relied (without independent investigation) upon certificates or comparable
documents of officers and representatives of the Company.

Based upon the foregoing, and in reliance thereon, and subject to the
limitations, qualifications and exceptions set forth herein, we are of the
following opinion:

1.    When the New Notes have been duly authenticated by The Bank of New York
Trust Company, N.A., in its capacity as Trustee, and duly executed and delivered
on behalf of the Company as contemplated by the Registration Statement, the New
Notes will be legally issued and will constitute binding obligations of the
Company, enforceable against the Company in accordance with their terms.

2.    When (a) the New Notes have been executed, authenticated, issued and
delivered in accordance with the provisions of the Indenture upon the exchange
and (b) the New Guarantees have been duly endorsed on the New Notes, the New
Guarantees will constitute binding obligations of the Guarantors enforceable
against the Guarantors in accordance with their terms.

Our opinions set forth above are subject to applicable bankruptcy, insolvency,
reorganization, fraudulent conveyance and transfer, moratorium or other laws now
or hereafter in effect relating to or affecting the rights or remedies of
creditors generally and by general principles of equity (whether applied in a
proceeding at law or in equity) including, without limitation, standards of
materiality, good faith and reasonableness in the interpretation and enforcement
of contracts, and the application of such principles to limit the availability
of equitable remedies such as specific performance.

We are members of the Bar of the State of New York, and accordingly, do not
purport to be experts on or to be qualified to express any opinion herein
concerning the laws of any jurisdiction other than laws of the State of New York
and the Delaware General Corporation Law and the Delaware Limited Liability
Company Act.

We hereby consent to being named as counsel to the Company and the Guarantors in
the Registration Statement, to the references therein to our Firm under the
caption "Legal Matters" and to the inclusion of this opinion as an exhibit to
the Registration Statement. In giving this consent, we do not thereby admit that
we are within the category of persons whose consent is required under Section 7
of the Securities Act, or the rules and regulations of the Commission
thereunder.
<PAGE>
AirGate PCS, Inc.
January 21, 2005
Page 4

Very truly yours,

/s/ Paul, Hastings, Janofsky & Walker, LLP

PAUL, HASTINGS, JANOFSKY & WALKER, LLP
<PAGE>
AirGate PCS, Inc.
January 21, 2005
Page 5

SCHEDULE 1

Guarantors
----------
AGW Leasing Company, Inc.
AirGate Network Services, LLC
AirGate Service Company, Inc.

