<PAGE>

                                                                   EXHIBIT 10.13

                         CYPRESS COMMUNICATIONS, INC.
                              Series C Preferred
                           Stock Purchase Agreement


     This Series C Preferred Stock Purchase Agreement (the "Agreement") is
                                                            ---------
entered into as of December 1, 1999, by and among CYPRESS COMMUNICATIONS, INC.,
a Delaware corporation (the "Company"), and each of those persons and entities,
                             -------
severally and not jointly, whose names are set forth on the Schedule of
Purchasers attached hereto as Exhibit A (collectively the "Purchasers" and
                              ---------                    ----------
individually a "Purchaser").
                ---------

     In consideration of the mutual promises hereinafter set forth, the parties
hereto agree as follows:

     1.   Agreement to Sell and Purchase

          1.1  Authorization of Shares.  The Company has authorized the sale and
issuance to the Purchasers of shares of its Series C Preferred Stock (the
"Shares") having the rights, preferences, privileges and restrictions set forth
 ------
in the Second Amended Certificate of Designation of Series A Preferred Stock,
Amended Certificate of Designation of Series B Preferred Stock and Series B-1
Preferred Stock, and Certificate of Designation of Series C Preferred Stock and
Series C-1 Preferred Stock of the Company, attached hereto as Exhibit B (the
                                                              ---------
"Certificate").
 -----------

          1.2  Sale and Purchase.  Subject to the terms and conditions hereof,
at the Closing (as hereinafter defined) the Company hereby agrees to issue and
sell to each Purchaser and each Purchaser severally and not jointly agrees to
purchase from the Company, the number of Shares set forth opposite such
Purchaser's name on Exhibit A, at a purchase price of nineteen dollars ($19.00)
                    ---------
per Share.

     2.   Closing, Delivery and Payment

     The closing of the sale and purchase of the Shares under this Agreement
(the "Closing") shall take place at 10:00 a.m. on December 1, 1999, at the
      -------
offices of Powell, Goldstein, Frazer & Murphy LLP, 191 Peachtree Street, N.E.,
Atlanta, Georgia 30303, or at such other time or place as the Company and the
Purchasers may mutually agree (such date is hereinafter referred to as the
"Closing Date"). At the Closing, subject to the terms and conditions hereof, the
 ------------
Company will deliver to the Purchasers certificates representing the number of
Shares to be purchased at the Closing by each Purchaser, against payment of the
purchase price therefor by certified check or wire transfer of immediately
available funds.

     3.   Representations and Warranties of the Company

     The Company hereby represents and warrants to, and agrees with, each
Purchaser as follows:
<PAGE>

          3.1  Organization, Good Standing and Qualification.  The Company is a
corporation duly organized, validly existing and in good standing under the laws
of the State of Delaware.  The Company has all requisite corporate power and
authority to own and operate its properties and assets, to execute and deliver
this Agreement and the Third Amended and Restated Stockholders Agreement as
amended by the First Amendment and the Second Amendment thereto, each of which
is attached hereto as Exhibit C (collectively, the "Stockholders Agreement"), to
                      ---------                     ----------------------
issue and sell the Shares and the shares of common stock, par value $0.001 per
share, of the Company  (the "Common Stock") issuable upon conversion of the
                             ------------
Shares (the "Conversion Shares"), to carry out the other provisions of this
             -----------------
Agreement and the Stockholders Agreement and the transactions contemplated
hereby and thereby, and to carry on its business as presently conducted and as
presently proposed to be conducted.  The Company is duly qualified to transact
business and is in good standing in each jurisdiction in which the failure to so
qualify could have a material adverse effect on the business, properties,
operations, earnings, assets or liabilities, condition (financial or otherwise)
(collectively, the "Condition") of the Company.
                    ---------

          3.2  Capitalization.

               (a)  The authorized capital stock of the Company, immediately
after the Closing, will consist of (i) Ten Million Eight Hundred Ninety-Four
Thousand Seventy-One and 62/100 (10,894,071.62) shares of Common Stock, Five
Hundred Eighty Five Thousand Nine Hundred Eighty and 46/100 (585,980.46) shares
of which are issued and outstanding, and (ii) Seven Million Six Hundred Eighty-
Seven Thousand Seven Hundred Four and 16/100 (7,687,704.16) shares of Preferred
Stock, of which One Million Two Hundred Eleven Thousand One Hundred Forty
(1,211,140) are designated as Series A Preferred Stock (the "Series A
                                                             --------
Preferred"), all of which are issued and outstanding, One Million Nine Hundred
---------
Nineteen Thousand One Hundred Eighty Eight (1,919,188) are designated as Series
B Preferred Stock (the "Series B Preferred"), One Million Three Hundred Thirty
                        ------------------
Nine Thousand Five Hundred Seventy Five (1,339,575) of which are issued and
outstanding, Five Hundred Seventy Nine Thousand Six Hundred Thirteen (579,613)
are designated as Series B-1 Preferred Stock (the "Series B-1 Preferred"), all
                                                   --------------------
of which are issued and outstanding, Three Million Nine Hundred Seventy Seven
Thousand Seven Hundred Sixty Three and 16/100 (3,977,763.16) are designated as
Series C Preferred Stock (the "Series C Preferred"), Three Million Four Thousand
                               ------------------
Seventy-Eight and 95/100 (3,004,078.95) of which were issued and outstanding as
of November 30, 1999 (the Series A Preferred, Series B Preferred, Series B-1
Preferred and Series C Preferred are collectively referred to herein as the
"Preferred Stock").
 ---------------

               (b)  Except as specifically set forth on Schedule 3.2 attached
                                                        ------------
hereto, and except for conversion rights of issued and outstanding shares of
Preferred Stock, as of the Closing Date, the Company will not (i) have
outstanding any capital stock or other securities convertible into or
exchangeable for any shares of its capital stock and, except for the preemptive
rights contained in the Stockholders Agreement, no person will have any right to
subscribe for or to purchase (including conversion or preemptive rights), or any
warrants or options for the purchase of, or any agreements providing for the
issuance (contingent or otherwise) of, or any calls, commitments or other claims
of any character relating to, any capital stock or any stock or securities
convertible into or exchangeable for any capital stock of the Company; (ii) have
any capital stock, equity interests or other securities reserved for issuance
for any purpose; or

                                       2
<PAGE>

(iii) except for the redemption rights set forth in the Certificate, be subject
to any obligation (contingent or otherwise) to repurchase or otherwise acquire
or retire any shares of its capital stock or any convertible securities, rights
or options of the type described in the preceding clause (i). No outstanding
options, warrants or other securities directly or indirectly exercisable for or
convertible into any class or series of the Company's capital stock require
anti-dilution adjustments by reason of the transactions contemplated by this
Agreement. All of the issued and outstanding shares of Common Stock and
Preferred Stock have been duly and validly issued, are fully paid and
nonassessable and were issued in compliance with all applicable federal and
state securities laws and any applicable preemptive rights. All of the
outstanding options, warrants and other securities of the Company have been
issued in compliance with all applicable federal and state securities laws and
any applicable preemptive rights. To the best knowledge of the Company, there
are no agreements among the Company's stockholders with respect to the voting or
transfer of the Company's capital stock, other than the agreements regarding
voting and transfer contained in the Stockholders Agreement. Schedule 3.2 sets
                                                             ------------
forth a complete and correct list of (i) the name of each of the Company's
stockholders and the number of shares and class and series of capital stock
owned by such stockholder, and (ii) the name of each holder of an outstanding
stock option and/or warrant, and the number of options and/or warrants to
purchase capital stock owned by such holder (and the applicable class and series
of capital stock) and the exercise price at which such option(s) or warrants may
be exercised.  The Company does not own or control, directly or indirectly, any
interest in any other corporation, association, or other business entity.

          3.3  Authorization; Binding Obligations.  All corporate action on the
part of the Company, its officers, directors and stockholders necessary for the
authorization, execution and delivery of this Agreement, the Stockholders
Agreement, the Certificate and each other document or instrument executed by the
Company, or any of its officers, in connection herewith or therewith or pursuant
hereto or thereto (this Agreement, together with all of the foregoing documents
and instruments, are sometimes collectively referred to herein as the "Company's
                                                                       ---------
Documents"), the performance of all obligations of the Company under the Company
---------
Documents and for the authorization, sale, issuance and delivery of the Shares
has been taken.  When issued in compliance with the provisions of this
Agreement, the Shares will be duly authorized, validly issued, fully paid and
nonassessable, free of any liens, preemptive or similar rights, or any other
encumbrances (except as set forth in the Stockholders Agreement) and issued in
compliance with all applicable state and federal securities laws.  The
Conversion Shares have been duly authorized and validly reserved for issuance
and, when issued upon conversion of the Series C Preferred, will be validly
issued, fully paid and nonassessable, free of any liens, preemptive or similar
rights, or any other encumbrance (except as set forth in the Stockholders
Agreement).  This Agreement, the Stockholders Agreement and the other Company's
Documents have been duly executed and delivered by the Company and constitute
legal, valid and binding obligations of the Company enforceable in accordance
with their terms.

          3.4  Consents and Approvals.  Except as set forth on Schedule 3.4, no
                                                               ------------
filings with, notices to, or approvals of any governmental or regulatory body
are required to be obtained or made by the Company in connection with the
consummation of the transactions contemplated hereby, including, without
limitation, the issuance of the Shares and the Conversion Shares.

                                       3
<PAGE>

          3.5  No Violations.  Except as set forth on Schedule 3.5, the
                                                      ------------
execution, delivery and performance of this Agreement and the other Company's
Documents and the performance by the Company of its obligations hereunder and
thereunder (i) do not and will not conflict with or violate any provision of the
certificate of incorporation or bylaws of the Company and (ii) do not and will
not (a) conflict with or result in a breach of the terms, conditions or
provisions of, (b) constitute a default under, (c) result in the creation of any
encumbrance upon the capital stock or assets of the Company pursuant to, (d)
give any third party the right to modify, terminate or accelerate any obligation
under, (e) result in a violation of, or (f) require any authorization, consent,
approval, exemption or other action by or notice to any court, governmental
authority, department, commission, board, bureau, agency or instrumentality,
domestic or foreign ("Governmental Authority"), or any other individual,
                      ----------------------
partnership, corporation, unincorporated organization or association, limited
liability company, trust or other entity (collectively, a "Person") pursuant to
                                                           ------
any law, statute, rule or regulation or any agreement, contract or instrument or
any order, judgment or decree to which the Company is subject or by which any of
its assets are bound.

          3.6  Financial Statements; Interim Changes. The Company's audited
balance sheet as of December 31, 1998, audited statements of operations, and
cash flows for the period ended December 31, 1998, unaudited balance sheet as of
September 30, 1999 (the "Latest Balance Sheet") and unaudited statements of
                         --------------------
income and cash flows of the Company for the period ended September 30, 1999,
(copies of which have been furnished to the Purchasers in connection with the
investment contemplated hereby) are complete and correct in all material
respects, have been prepared in accordance with generally accepted accounting
principles ("GAAP") consistently applied (subject to, in the case of unaudited
             ----
statements, normal year-end adjustments and the absence of footnote disclosures,
all of which are not material) and fairly present in all material respects the
financial position, the results of operations and cash flows of the Company for
the period covered thereby.  The Company has no material liabilities or
obligations of any nature (absolute, accrued, contingent or otherwise) that are
not either reflected or fully reserved against on the Latest Balance Sheet or
incurred in the ordinary course of the business of the Company subsequent to the
date thereof.  Since the date of the Latest Balance Sheet, there has not been
any material adverse change in the Condition of the Company.

          3.7  Compliance with Laws.  The Company's business has been conducted
in compliance with all applicable laws and regulations of Governmental
Authorities, except for such violations that have been cured or that,
individually or in the aggregate, could not reasonably be expected to have a
material adverse effect on the Condition of the Company.  The Company has all
permits, licenses, orders, certificates, authorizations and approvals of any
Governmental Authority (collectively, the "Permits") that are material to the
                                           -------
conduct of its business as presently conducted and as proposed to be conducted;
all such Permits are, and as of the Closing will be, in full force and effect;
no violations or notices of failure to comply have been issued or recorded in
respect of any such Permits; and the Company has no knowledge of any reason why
such Permits may be revoked or suspended. To the best of the Company's
knowledge, the business, operations, assets and properties of the Company are
and have been operated and maintained in compliance in all material respects
with all applicable federal, state, city, county and local environmental
protection laws and regulations.

                                       4
<PAGE>

          3.8   Proprietary Rights.  The Company has not received any
communications alleging that it has violated or, by conducting its business as
proposed would violate, any proprietary rights of any other person, and except
as set forth on Schedule 3.8, the Company is not aware of any basis for the
                ------------
foregoing.

          3.9   Actions Pending.  Except as set forth on Schedule 3.9, there is
                                                         ------------
no action, suit, investigation, proceeding or governmental approval process
(collectively, "Actions") pending or, to the best knowledge of the Company,
                -------
threatened against or affecting the Company or any of its properties or rights
before any court or by or before any governmental body or arbitration board or
tribunal, none of which could reasonably be expected to have a material adverse
effect on the Condition of the Company.

          3.10  Material Contracts.  Except as set forth on Schedule 3.10
                                                            -------------
attached hereto, the Company is not a party to (and is not otherwise bound by)
any of the following:  (i) any employment or consulting agreement, (ii) any
agreement providing for the issuance or repurchase of any securities of the
Company, (iii) any agreement in respect of registration rights, preemptive
rights, rights of first refusal, voting rights or other rights of security
holders (other than the Stockholders Agreement), (iv) any agreement evidencing
or providing for any indebtedness for borrowed money, any agreement with any
past or present officer, director, key employee or shareholder of the Company or
any affiliate or relative thereof (other than the Stockholders Agreement and
grant agreements with respect to Reserved Employee Stock), or (v) any other
agreement that could reasonably be deemed material to the Company or its
Condition.

          3.11  Insurance.  The Company has in full force and effect liability
insurance of the types and providing coverage in such amounts as is customary
for companies of established reputation engaged in the same or similar business
and similarly situated, and such other insurance policies as are sufficient for
compliance with all requirements of law and applicable agreements.

          3.12  Investments in United States Real Property Interests.  The
Company's capital stock does not constitute a United States real property
interest as that term is defined in Section 897(c)(1)(A)(ii) of the Internal
Revenue Code of 1986, as amended (the "Code").  The preceding representation is
                                       ----
based on a determination by the Company that the Company is not and has never
been a United States real property holding corporation (as that term is defined
in Section 897(c)(2) of the Code).  From time to time, upon request of any
Purchaser, the Company shall make a determination as to its status as a United
States real property holding corporation ("USRPHC").  If at any time in the
                                           ------
future the Company should become a USRPHC, the Company shall, as promptly as
possible, notify each Purchaser of such change in status.

          3.13  Unrelated Business Taxable Income.  Any gross income derived by
the Purchasers from the Company shall be in the form of dividends, interest,
capital gains and losses from the disposition of property, rents and royalties,
but only such rents and royalties as are excluded pursuant to Code Sections
512(b)(2) and 512(b)(3), respectively, in calculating unrelated business taxable
income and only such dividends, interest, capital gains and losses, and rents
and royalties that are not included under Section 512(b)(4) of the Code in
calculating unrelated business taxable income.  This Section 3.13 shall not be
deemed to apply to (i) any compensation (in cash, stock or other form) received
by designees of the Purchasers in their

                                       5
<PAGE>

capacities as directors of the Company that is transferred to the Purchasers, or
(ii) any income included under Section 512(b)(4) of the Code as a result of
acquisition indebtedness incurred by any Purchaser in connection with the
purchase of an interest in the Company, or (iii) any income derived by the
Purchasers from the Company with respect to which the Purchasers have expressly
waived in writing the application of the provision of this Section 3.13, or (iv)
any income derived by the Purchasers pursuant to the reimbursement of expenses
pursuant to Section 7 hereof.

          3.14  Books and Records.  The minute books of the Company fully set
forth all material action taken by the Board of Directors, stockholders and, if
any, executive board (or other committee thereof) of the Company.

          3.15  Disclosure.  The Company has fully provided each Purchaser with
all the information which such Purchaser has requested for deciding whether to
purchase the Shares.  Neither this Agreement nor any other certificates made or
delivered in connection herewith contains any untrue statement of a material
fact or omits to state a material fact necessary to make the statements herein
or therein not misleading.

          3.16  Year 2000.  The Company has reviewed its operations to evaluate
the extent to which the business or operations of the Company will be affected
by the Year 2000 Problem (as defined below).  As a result of such review, the
Company has no reasonable basis to believe, and does not believe, that the Year
2000 Problem will have a material adverse effect on the Condition of the
Company; provided, however, that the Company does not make any representation or
warranty as to the operation of any telecommunications network operated by an
incumbent or competing local exchange carrier which may be affected by the Year
2000 Problem.  The "Year 2000 Problem" as used herein means any significant risk
                    -----------------
that computer hardware or software used in the receipt, transmission,
processing, manipulation, storage, retrieval, retransmission or other
utilization of data or in the operation of mechanical or electrical systems of
any kind will not, in the case of dates or time periods occurring after December
31, 1999, function at least as effectively as in the case of dates or time
periods occurring prior to January 1, 2000.

          3.17  Environmental Matters.

                (a) To the best of the Company's knowledge, the Company has not
caused or allowed, nor has the Company contracted with any party for, the
generation, use, transportation, treatment, storage or disposal of any Hazardous
Substances (as defined below) in connection with the operations of its business
or otherwise.

                (b) To the best of the Company's knowledge, the Company, the
operations of its business, and any real property that the Company owns, leases,
or otherwise occupies (the "Premises") are in compliance in all material
respects with all applicable Environmental Laws (as defined below) and orders or
directives of any governmental authorities having jurisdiction under such
Environmental Laws including, without limitation, any Environmental Laws or
orders or directives with respect to any cleanup or remediation of any release
or threat of release of Hazardous Substances.

                                       6
<PAGE>

               (c)  To the best of the Company's knowledge, the Company has not
received any citation, directive, letter or other communication, written or
oral, or any notice of any proceedings, claims or lawsuits, from any person,
entity or governmental authority arising out of the occupation of the Premises
or the conduct of its operations, nor is it aware of any reasonable basis
thereof.

               (d)  To the best of the Company's knowledge, the Company has
obtained and is maintaining in full force and effect all material permits,
licenses and approvals required of the Company by any Environmental Laws
applicable to the Premises and the business operations conducted by the Company
and is in compliance with all such permits, licenses and approvals, in all
material respects.

               (e)  To the best of the Company's knowledge, the Company has not
caused or allowed a release of any Hazardous Substance unto, nor to the best of
the Company's knowledge has the Premises or any property at or near the Premises
ever been subject to a release, or a threat of a release, of any Hazardous
Substance.

               (f)  The term "Environmental Laws" shall mean any federal, state
or local law, ordinance or regulation pertaining to the protection of human
health or the environment including, without limitation, the Comprehensive
Environmental Response, Compensation and Liability Act, 42 U.S.C. Sections 9601,
et seq., Emergency Planning and Community Right-to-Know Act, 42 U.S.C. Sections
11001, et seq., and the Resource Conservation and Recovery Act, 42 U.S.C.
Sections 6901, et seq.

               (g)  The term "Hazardous Substance" includes oil and petroleum
products, asbestos, polychlorinated biphenyls and urea formaldehyde, and any
other materials classified as hazardous or toxic under any Environmental Laws.

     4.   Representations And Warranties Of The Purchasers

     Each Purchaser severally and not jointly hereby represents and warrants to
the Company as follows:

          4.1  Requisite Power and Authority.  Such Purchaser has all necessary
partnership or limited liability company power and authority under all
applicable provisions of law to execute and deliver this Agreement and to carry
out its provisions. All actions on such Purchaser's part required for the lawful
execution and delivery of this Agreement have been or will be effectively taken
prior to the Closing.

          4.2  Investment Representations.  Such Purchaser understands that
neither the Shares nor the Conversion Shares have been registered under any
state securities act or the Securities Act of 1933, as amended (the "Securities
                                                                     ----------
Act").  Such Purchaser also understands that the Shares are being offered and
---
sold pursuant to an exemption from registration contained in applicable state
securities acts and the Securities Act based in part upon the Purchaser's
representations contained in this Agreement.

               (a)  Purchaser Bears Economic Risk. Such Purchaser has
substantial experience in evaluating and investing in private placement
transactions of securities in

                                       7
<PAGE>

companies similar to the Company so that Purchaser is capable of evaluating the
merits and risks of its investment in the Company and has the capacity to
protect its own interests. Such Purchaser must bear the economic risk of this
investment indefinitely unless the Shares (or the Conversion Shares) are
registered pursuant to the Securities Act, or an exemption from registration is
available. Such Purchaser understands that the Company has no present intention
of registering the Shares or the Conversion Shares. Such Purchaser also
understands that there is no assurance that any exemption from registration
under the Securities Act will be available and that, even if available, such
exemption may not allow such Purchaser to transfer all or any portion of the
Shares or the Conversion Shares under the circumstances, in the amounts or at
the times such Purchaser might propose. Such Purchaser can bear the economic
risk of losing its entire investment in the Company.

               (b)  Acquisition for Own Account. Such Purchaser is acquiring the
Shares and the Conversion Shares for Purchaser's own account for investment
only, and not with a view towards their resale or distribution in violation of
applicable securities laws.

               (c)  Purchaser Can Protect Its Interest. Such Purchaser
represents that, by reason of Purchaser's or of its management's business or
financial experience, such Purchaser has the capacity to protect its own
interests in connection with the transactions contemplated in this Agreement. In
making this representation, the Purchaser is relying upon the provisions of the
Certificate and of this Agreement.

               (d)  Accredited Investor. Such Purchaser represents that
Purchaser is an accredited investor within the meaning of Regulation D under the
Securities Act.

               (e)  Company Information. Such Purchaser has had an opportunity
to discuss the Company's business, management and financial affairs with
directors, officers and management of the Company. Such Purchaser has also had
the opportunity to ask questions of, and receive answers from, the Company and
its management regarding the terms and conditions of this investment. Purchaser
has had an adequate opportunity to inspect and copy all material documents
relating to the Company which it has requested and has been furnished or
provided access to information similar to that which would be included in a
registration statement as is necessary for such Purchaser, in view of its
business or management experience and sophistication, to evaluate the merits and
risks of an investment in the Company.

               (f)  Rule 144. Such Purchaser acknowledges and agrees that the
Shares and the Conversion Shares must be held indefinitely unless they are
subsequently registered under the Securities Act or an exemption from such
registration is available. Such Purchaser has been advised or is aware of the
provisions of Rule 144 promulgated under the Securities Act, which permits
limited resale of shares purchased in a private placement subject to the
satisfaction of certain conditions, including, among other things: the
availability of certain current public information about the Company, the resale
occurring not less than one year after a party has purchased and paid for the
security to be sold, the sale being through an unsolicited "broker's
transaction" or in transactions directly with a market maker (as said term is
defined under the Securities Exchange Act of 1934, as amended) and the number of
shares being sold during any three-month period not exceeding specified
limitations.

                                       8
<PAGE>

               (g)  Risks. Such Purchaser acknowledges that the following risks
relating to an investment in the Company have been disclosed to such Purchaser
by the Company.

                    (i)    The Company was formed in 1995 and therefore has a
limited operating history upon which an evaluation of the Company's performance
could be based. There can be no assurance that the Company's operations will be
profitable or that the Company will be able to sell its products and services at
price levels that will produce profits or an acceptable return to shareholders.

                    (ii)   Additional financing may be required to support the
growth activities of the Company. The Company may need financing for operations
and marketing. No arrangements have been made to secure such financing, and
there can be no assurance that such additional financing will be available when
required or on terms acceptable to the Company.

                    (iii)  The telecommunications industry has been
characterized by steady technological change, frequent new service
introductions, evolving industry standards, and new and consolidating
competitors. The Company's success will depend in part on its ability to
anticipate such changes and to offer responsive services on a timely basis.
Further, although the trend has been toward decreases in the cost of equipment
and network elements, there is no assurance that these trends will continue, or
that the Company will be able to respond successfully to such changes.

                    (iv)   The telecommunications industry is highly regulated.
In the future, certain aspects of the Company's operations may require
authorization from the Federal Communications Commission ("FCC") and/or
                                                           ---
applicable state public service commissions. This may involve both obtaining the
required authorizations and complying with the on-going requirements imposed on
carriers, such as filing a tariff. No assurances can be given that there will be
no opposition to the Company's applications or that the necessary authorizations
(other than any such authorization necessary to continue the current business
operations of the Company) will be granted. Additional expenses (such as legal
and accounting fees) will be involved in attempting to obtain and in maintaining
these authorizations and in complying with the accounting reporting and
administrative regulations imposed by the FCC and the state commissions. The
cost for access to local service could change significantly as deregulation of
the local loop progresses and carriers other than the existing local exchange
carriers are authorized to provide local service.

                    (v)    The Company competes with a number of companies with
significantly greater financial resources than the Company.

                    (vi)   The Company's success will be related to the real
estate cycle, in particular, to construction and leasing activity.

                    (vii)  The Company's operations will depend in part upon
contractual arrangements with local exchange and long distance carriers. The
costs associated with the purchase of local exchange services, access to the
long distance network, and long distance services could change significantly as
deregulation of the local loop progresses, carriers

                                       9
<PAGE>

other than the existing local exchange carriers are authorized to provide local
exchange service and access to long distance, and the costs of long distance
carriers change in response. The Company believes it will have a number of
options for obtaining both exchange and access services at competitive rates,
however the continuing availability of alternative resources cannot be assured.

                    (viii) The Company has used and will, for the foreseeable
future, use incumbent local exchange carriers ("ILECs") to provide the bulk of
                                                -----
inbound calling services to telephone numbers used by the Company's customers.
Because local number portability (i.e., the regulatory and technical abilities
of the Company and/or the Company's customers to transfer telephone numbers
freely between local exchange carriers) was delayed nationwide and is far from a
failsafe procedure where it has been implemented, the Company is dependent on
the quality of such ILEC services for completing telephone calls, both local and
long distance, intended for the Company's customers. Should such services prove
to be of poor quality for any particular building or market in which the Company
operates, the business of the Company in that building or in that market could
be adversely affected in a material manner.

                    (ix)   The Company uses several competitive local exchange
carriers ("CLECs") to provide outbound local, point to point and local loop
           -----
services, in addition to using ILECs. Though the Company believes that this
diversification of vendors has the potential to reduce its cost of such
services, as well as provide operational redundancy, there is a heightened
element of operational risk associated with using services from new vendors.

                    (x)    A search done in the process of preparing to apply
for a trademark for the name of the Company revealed potential conflicts with
the Company's use of the trade name "Cypress" and the Company's ability to
obtain trademark protection for this name. The Company has decided that it is
not in the Company's best interest to apply for a trademark in the name of
Cypress Communications or to change the name of the Company at this time.
Furthermore, there is a possibility that one of the firms with whom there is a
potential conflict, or other companies for that matter, will demand that the
Company discontinue using the name Cypress Communications. Such a demand might
result in either expensive litigation and/or a change in the Company's name,
which in either event, could have a material adverse effect on the Company.

               (h)  Residence. The address of such Purchaser as set forth on
Exhibit A attached hereto is its true and correct principal place of business.
---------

               (i)  HSR Matters. Purchaser is not included within any other
person (within the meaning of the Hart-Scott-Rodino Improvements Act of 1976, as
amended ("HSR Act")) who is also a Purchaser or who otherwise owns voting
          -------
securities of the Company.

     Nothing contained in this Section 4 shall in any respect limit or modify
the representations and warranties of the Company in Section 3 of this Agreement
or the right of each Purchaser to rely thereon.

                                       10
<PAGE>

     5.   Conditions Precedent To Purchasers' Obligations

     The obligation of each Purchaser to purchase and pay for the Shares to be
delivered to it at the Closings shall be subject to the satisfaction of the
following conditions as of the applicable Closing Date:

               (a)  the representations and warranties of the Company contained
in this Agreement shall be true and correct as if made on and as of the Closing
Date;

               (b)  the Company, the Purchasers and the existing stockholders of
the Company shall have entered into the Stockholders Agreement in the form of
Exhibit C attached hereto;
---------

               (c)  the Purchasers shall have received the legal opinion of
Powell, Goldstein, Frazer & Murphy LLP, counsel to the Company, substantially in
the form of Exhibit D;
            ---------

               (d)  all other Purchasers shall have concurrently purchased the
Shares to be purchased by them pursuant to this Agreement;

               (e)  all authorizations, approvals or permits, if any, of any
Governmental Authority that are required in connection with and prior to the
lawful issuance and sale of the Shares or Conversion Shares shall be duly
obtained and effective as of the Closing Date;

               (f)  all corporate and other proceedings in connection with the
transactions contemplated at the Closing and all documents incident thereto
shall be reasonably satisfactory in form and substance to each Purchaser at the
Closing, and they shall have received all such counterpart original and
certified or other copies of such documents as they may reasonably request;

               (g)  no action, proceeding, investigation, regulation or
legislation shall have been instituted, threatened or proposed before any court,
Governmental Authority or legislative body to enjoin, restrain, or prohibit, or
to obtain substantial damages in respect of, or which is related to or arises
out of this Agreement or the consummation of the transactions contemplated
hereby or thereby, or which, in Purchaser's reasonable discretion, would make it
advisable to consummate the transactions contemplated by this Agreement;

               (h)  the Company shall have executed and delivered to Purchaser a
Stock Warrant Agreement substantially in the form of Exhibit E; and
                                                     ---------

               (i)  the Certificate shall have been duly adopted by the Company
and filed with the Secretary of State of the State of Delaware and shall be in
effect.

     6.   Covenants

     The Company covenants and agrees with the Purchasers as follows:

                                       11
<PAGE>

          6.1  Assistance in Sales.  Anything in this Agreement or the
Stockholders Agreement to the contrary notwithstanding, in the event that it
becomes unlawful for any Purchaser to continue to hold all or some portion of
the Shares to be held by it, or restrictions are imposed on such Purchaser by
any law, rule or regulation which, in the reasonable judgement of such
Purchaser, make it unduly burdensome to continue to hold all or some portion of
such Shares, then such Purchaser may sell or otherwise dispose of all or any
portion of its Shares and Conversion Shares, and the Company, at no expense to
the Company, shall use reasonable efforts to assist such Purchaser in disposing
of such interest in a prompt and orderly manner, and, at the reasonable request
of any such Purchaser, shall provide (and authorize such Purchaser to provide)
financial and other information concerning the Company to any prospective
purchaser of such interest.

          6.2  Real Property Holding Corporation.  The Company covenants that it
will use reasonable commercial efforts not to become a USRPHC.  The Company
agrees to make determinations as to its status as a USRPHC, and will file
statements concerning those determinations with the Internal Revenue Service, in
the manner and at the times required under Reg. (S) 1.897-2(h), or any
supplementary or successor provision thereto.  Within 30 days of a request from
a Purchaser or any of its partners, the Company will inform the requesting
party, in the manner set forth in Reg. (S) 1.897-2(h)(1)(iv) or any
supplementary or successor provision thereto, whether that party's interest in
the Company constitutes a United States real property interest (within the
meaning of Section 897(c)(1) of the Code and FIRPTA) and whether the Company has
provided to the Internal Revenue Service all required notices as to its USRPHC
status.  If at any time in the future the Company should become a USRPHC, the
Company shall, as promptly as possible, notify each Purchaser of such change in
status.

          6.3  Taxable REIT Subsidiary.  In the event that provisions similar to
the "taxable REIT subsidiary" provisions of H.R. 1180 are enacted, the Company
covenants that it will, upon written request by any Purchaser, make a "taxable
REIT subsidiary election" with respect to any affiliate of a Purchaser that such
Purchaser may designate.

          6.4  Notices of Redemptions or Conversions.

               (a)  The Company shall provide each holder of Series C Preferred
with written notice (specifying the class and number of shares to be redeemed)
promptly upon receiving any notice of redemption pursuant to Section 4(a) of the
Certificate.

               (b)  The Company shall provide each holder of Series C Preferred
with written notice (specifying the class and number of shares to be redeemed or
acquired) promptly upon determining that it shall redeem shares of Senior
Preferred or that it shall permit an affiliate to acquire shares of Senior
Preferred.

               (c)  The Company shall provide each holder of Series C Preferred
with written notice (specifying the class and number of shares to be converted)
promptly upon receiving any notice of optional conversion pursuant to Section
5(l)(i) of the Certificate.

          6.5  Limitations on Certain Actions.  Without the prior consent of
Purchaser, the Company will not (i) take any action which would cause the
Company or any successor

                                       12
<PAGE>

thereto to be treated as a partnership for federal income tax purposes, or (ii)
merge or consolidate with or into any entity that, following such merger or
consolidation, would be treated as a partnership for federal income tax
purposes.

     7.   Expense Reimbursement

     The Company hereby agrees to reimburse each of the Purchasers for their
reasonable out-of-pocket expenses incurred in connection with the transactions
contemplated hereby, including all reasonable expenses incurred in connection
with their due diligence examination of the Company, the preparation and
negotiation of this Agreement, the term sheet, the Stockholders Agreement and
all other documents evidencing the transactions contemplated herein (including
the fees (not to exceed $25,000 in the aggregate) and expenses of Sullivan &
Cromwell, counsel to the Purchasers, and Proskauer Rose LLP, counsel to the
Purchasers. The Company hereby agrees to reimburse such Purchaser for the legal
expenses, if any, incurred in connection with the filing of any documents
regarding the transactions contemplated by this Agreement with any Governmental
Authorities.

     8.   Miscellaneous

          8.1  Publicity.  Except as may be required by law, the Company shall
not use the name of, or make reference to, any Purchaser or any of its
affiliates in any press release or in any public manner without such Purchaser's
prior written consent.

          8.2  Indemnification.  The Company agrees to indemnify each Purchaser
and, to the extent named or involved in any claim, each officer, director,
employee, agent, partner, stockholder and affiliate of each Purchaser
(collectively, the "Indemnified Parties") for, and hold each Indemnified Party
                    -------------------
harmless from and against: (i) any and all damages, losses, claims and other
liabilities of any and every kind, including, without limitation, judgments and
costs of settlement, and (ii) any and all reasonable out-of-pocket costs and
expenses of any and every kind, including, without limitation, reasonable fees
and disbursements of counsel for such Indemnified Parties (all of which expenses
periodically shall be reimbursed as incurred), in each case, to the extent
arising out of or suffered or incurred in connection with any of the following:
(a) any misrepresentation or any breach of any warranty made by the Company
herein or in any of the other Company's Documents, (b) any breach or non-
fulfillment of any covenant or agreement made by the Company herein or in any of
the other Company's Documents, and (c) any claim relating to or arising out of a
violation of applicable federal or state securities laws by the Company in
connection with the sale of the Shares by the Company to the Purchasers.

          8.3  Governing Law.  This Agreement shall be governed in all respects
by the laws of the State of New York as such laws are applied to agreements
between New York residents entered into and performed entirely in New York.

          8.4  JUDICIAL PROCEEDINGS.  ANY JUDICIAL PROCEEDING INVOLVING ANY
DISPUTE, CONTROVERSY OR CLAIM ARISING OUT OF OR RELATING TO THIS AGREEMENT OR
THE BREACH OR ALLEGED BREACH OF THIS AGREEMENT (EACH OF THE FOREGOING DISPUTES,
CONTROVERSIES AND CLAIMS HEREINAFTER REFERRED TO AS AN "AGREEMENT DISPUTE"), MAY
                                                        -----------------
BE

                                       13
<PAGE>

BROUGHT IN A FEDERAL OR STATE COURT LOCATED IN NEW YORK COUNTY, IN NEW YORK
STATE, AND EACH OF THE PARTIES HERETO (i) UNCONDITIONALLY ACCEPTS THE
JURISDICTION OF SUCH COURTS AND ANY RELATED APPELLATE COURT AND IRREVOCABLY
AGREES TO BE BOUND BY ANY JUDGMENT RENDERED THEREBY AND (ii) IRREVOCABLY WAIVES
ANY OBJECTION SUCH PARTY MAY NOW HAVE OR HEREAFTER HAS AS TO THE VENUE OF ANY
SUCH PROCEEDING BROUGHT IN SUCH A COURT OR THAT SUCH COURT IS AN INCONVENIENT
FORUM. EACH OF THE PARTIES HERETO HEREBY WAIVES TRIAL BY JURY IN ANY JUDICIAL
PROCEEDING TO WHICH THEY ARE PARTIES INVOLVING AN AGREEMENT DISPUTE.

          8.5   Survival.  The representations, warranties, covenants and
agreements made herein shall survive any investigation made by any Purchaser and
the closing of the transactions contemplated hereby. All statements as to
factual matters contained in any certificate or other instrument delivered by or
on behalf of the Company pursuant hereto in connection with the transactions
contemplated hereby shall be deemed to be representations and warranties by the
Company hereunder solely as of the date of such certificate or instrument.

          8.6   Successors and Assigns.  Except as otherwise expressly provided
herein, the provisions hereof shall inure to the benefit of, and be binding
upon, the successors, assigns, heirs, executors and administrators of the
parties hereto and shall inure to the benefit of and be enforceable by each
person who shall be a holder of the Shares from time to time, except that
neither this Agreement nor any rights or obligations hereunder shall be assigned
or delegated by the Company without the prior written consent of the Purchasers.

          8.7   Entire Agreement.  This Agreement, the Exhibits, the Schedules
and the other documents expressly delivered pursuant hereto, including the
Stockholders Agreement, supersede any other agreement, whether written or oral,
that may have been made or entered into by the parties hereto relating to the
matters contemplated hereby and constitute the full and entire understanding and
agreement between the parties with regard to the subjects hereof, and no party
shall be liable or bound to any other in any manner by any representations,
warranties, covenants and agreements except as specifically set forth herein and
therein.

          8.8   Specific Enforcement.  Any Purchaser shall be entitled to
specific enforcement of its rights under this Agreement.  The Company
acknowledges that money damages would be an inadequate remedy for its breach of
this Agreement and consents to an action for specific performance or other
injunctive relief in the event of any such breach.

          8.9   Separability.  In case any provision of the Agreement shall be
invalid, illegal or unenforceable, the validity, legality and enforceability of
the remaining provisions shall not in any way be affected or impaired thereby.

          8.10  Amendment and Waiver.  This Agreement may be amended or modified
only upon the mutual written consent of the Company and all of the Purchasers.

          8.11  Notices.  All notices required or permitted hereunder shall be
in writing and shall be deemed effectively given: (i) upon personal delivery to
the party to be notified; (ii)

                                       14
<PAGE>

when sent by confirmed telex or facsimile if sent during normal business hours
of the recipient, if not, then on the next business day; (iii) five (5) days
after having been sent by registered or certified mail, return receipt
requested, postage prepaid; or (iv) one (1) day after deposit with a nationally
recognized overnight courier, special next day delivery, with verification of
receipt. All communications shall be sent to the Company at Fifteen Piedmont
Center, Suite 710, Atlanta, Georgia 30305, Attn.: President, with a courtesy
copy to Powell, Goldstein, Frazer & Murphy, L.L.P., 191 Peachtree Street, NE,
16/th/ Floor, Atlanta, Georgia 30303, Attention: William M. Ragland, Jr., and
James K. Wagner, Jr., and to a Purchaser at the address set forth on Exhibit A
                                                                     ---------
attached hereto or at such other address as the Company or Purchaser may
designate by ten (10) days advance written notice to the other parties hereto.

          8.12  Counterparts.  This Agreement may be executed in any number of
counterparts, each of which shall be an original, but all of which together
shall constitute one instrument.

          8.13  Broker's Fees.  Each party hereto severally and not jointly
represents and warrants that no agent, broker, investment banker, person or firm
acting on behalf of or under the authority of such party hereto is or will be
entitled to any broker's or finder's fee or any other commission directly or
indirectly in connection with the transactions contemplated herein. Each party
hereto further agrees to indemnify each other party for any claims, losses or
expenses incurred by such other party as a result of the representation it has
made in this Section 8.13 being untrue.

          8.14  Descriptive Headings.  The section and other headings contained
in this Agreement are for convenience of reference only and shall not affect the
meaning or interpretation of this Agreement.

          8.15  Understanding Among Purchasers.  The decision of each Purchaser
to purchase Shares pursuant to this Agreement has been made by such Purchaser
independently of any other Purchaser and independently of any statements or
opinions as to the Condition of the Company which may have been made or given by
any other Purchaser or by any agent or employee of any other Purchaser.  Each
Purchaser acknowledges that no other Purchaser has acted as agent for such
Purchaser in connection with making its investment hereunder and that no other
Purchaser will be acting as agent of such Purchaser in connection with
monitoring its investment hereunder.  Each Purchaser acknowledges that the
Company intends to issue up to $80,000,000 in shares of Series C Preferred Stock
(or Series C-1 Preferred Stock) in connection with this private placement,
including its ongoing licensing efforts.  Each Purchaser waives any pre-emptive
rights that it may have to participate in the sale of such additional shares of
Series C Preferred Stock (or Series C-1 Preferred Stock) pursuant to the
Stockholders Agreement or otherwise, provided that the Company sells such shares
of Series C Preferred Stock (or Series C-1 Preferred Stock) in connection with
its licensing efforts to parties who are not affiliated with the Purchasers or
other stockholders of the Company or, in the case of Mark H. Dunaway, an
existing stockholder of the Company, to Mr. Dunaway in an amount up to
approximately $160,000 of shares of Series C Preferred Stock, in each case on
substantially the same terms as are included herein.

                                       15
<PAGE>

          8.16  Future Financings.  Nothing contained in this Agreement or any
Purchaser's prior dealings with the Company shall be deemed to constitute a
commitment on the part of any Purchaser to participate in any future financings
by the Company.

          8.17  Business Day.  As used herein, the term "Business Day" shall
mean any day on which banks in New York City, Boston, Massachusetts, and San
Francisco, California, are open for the transaction of business.

                                   * * * * *

               [The rest of this page left intentionally blank]

                                       16
<PAGE>

     In Witness Whereof, the parties hereto have executed the Agreement as of
the date set forth in the first paragraph hereof.

                                   COMPANY:

                                   CYPRESS COMMUNICATIONS, INC.

                                   By: /s/ Barry L. Boniface
                                      -------------------------------
                                   Name: Barry L. Boniface
                                        -----------------------------
                                   Title: Chief Financial Officer
                                         ----------------------------


                                   PURCHASER:

                                   VORNADO COMMUNICATIONS, L.L.C.

                                   By:  Vornado Realty, L.P., its manager

                                   By:  Vornado Realty Trust, its general
                                        partner


                                   By: /s/ Irwin Goldberg
                                      -------------------------------
                                   Name: Irwin Golberg
                                        -----------------------------
                                   Title: Vice President, CFO
                                         ----------------------------