EXCHANGE AGREEMENT

Exhibit 10.7

EXCHANGE AGREEMENT

This EXCHANGE AGREEMENT (this “Agreement”), dated as of July 31, 2007, is made by and among ITC^DeltaCom, Inc., a Delaware corporation (“Parent”), Interstate FiberNet, Inc., a wholly-owned subsidiary of Parent and a Delaware corporation (the “Company”), and the investment funds managed by Tennenbaum Capital Partners, LLC identified on the signature pages hereto (individually, a “TCP Holder” and collectively, the “TCP Holders”).

RECITALS

WHEREAS, Parent, the Company, certain subsidiary guarantors of Parent, certain banks, financial institutions and other institutional lenders (including the TCP Holders), Tennenbaum Capital Partners, LLC (as agent), and TCP Agency Services, LLC (as collateral agent), entered into that certain Securities Purchase Agreement dated as of July 26, 2005, whereby the Company issued third lien, senior secured notes due September 2009 (the “Third Lien Notes”) in the aggregate principal amount of $50.8 million to various investors, including the TCP Holders; and

WHEREAS, the Third Lien Notes are supported by Parent’s full and unconditional guarantee; and

WHEREAS, Parent intends to consummate a recapitalization of its capital structure as described in Exhibit A annexed hereto (the “Recapitalization”); and

WHEREAS, on June 8, 2007, the TCP Holders entered into a commitment letter whereby they confirmed, among other things, their intention to exchange or convert $25 million principal amount of Third Lien Notes (the “TCP Third Lien Notes”) and all preferred stock and warrants of Parent held by them for common stock of Parent, par value $0.01 per share (the “Common Stock”) in connection with the Recapitalization, which commitment letter was later amended by a supplemental commitment letter and lock-up agreement dated as of July 16, 2007 (the Stockholder Lock-Up Agreement”); and

WHEREAS, subject to the terms and conditions of this Agreement, the TCP Holders agree to exchange the TCP Third Lien Notes for Common Stock, and Parent agrees to issue to the TCP Holders shares of Common Stock in exchange for the TCP Third Lien Notes.

NOW, THEREFORE, in consideration of the premises and covenants and agreements contained herein, the parties hereto agree as follows:

ARTICLE I

EXCHANGE OF THIRD LIEN NOTES

Section 1.1. Exchange of Notes. Upon the terms and subject to the conditions set forth herein, the TCP Holders hereby agree to exchange their TCP Third Lien Notes for, and Parent hereby agrees to issue and deliver to the TCP Holders in exchange for such notes, a total of 8,259,193 shares of Common Stock (the “TCP Third Lien Notes Conversion”). Schedule 1

1

hereto lists, as the date of this Agreement, (i) each TCP Holder, (ii) the amount of TCP Third Lien Notes held by each TCP Holder as of the Closing Date as reflected in the Company’s books and records, (iii) the total amount of TCP Third Lien Notes that will be exchanged, (iv) the amount of cash to be received by each TCP Holder for Third Lien Notes they own that are not being converted to Common Stock, and (v) the total number of Common Stock that are being issued to such TCP Holder upon effectiveness of the TCP Third Lien Notes Conversion (the “Conversion Shares”). The TCP Third Lien Notes Conversion will be effective, and the TCP Holders will be deemed to be the holders of the Conversion Shares, as of the closing date of the Recapitalization (the “Closing Date”).

Section 1.2. Deliveries.

(a) On the Closing Date, each TCP Holder shall tender to the Company for cancellation all TCP Third Lien Notes held by such TCP Holder, duly endorsed in blank.

(b) Promptly after the Closing Date, Parent shall deliver, or cause Parent’s transfer agent for the Conversion Shares to deliver, to each TCP Holder a share certificate or certificates, each registered in the name of such TCP Holder, representing the Conversion Shares.

ARTICLE II

REPRESENTATIONS AND WARRANTIES OF THE TCP HOLDERS

As of the Closing Date, each TCP Holder represents and warrants to Parent and the Company, as follows:

Section 2.1. Acquisition for Investment. Each TCP Holder is acquiring the Conversion Shares for its own account, for investment and not with a view to, or for sale in connection with, the distribution thereof within the meaning of the Securities Act of 1933, as amended (the “Securities Act”) (it being understood that except as otherwise provided in this Agreement, the TCP Holder does not agree to hold the Conversion Shares for any minimum or other specific term and reserves the right to dispose of the Conversion Shares at any time in accordance with the Securities Act and state securities laws applicable to such disposition).

Section 2.2 Accredited Investor Status. Each TCP Holder is an “accredited investor,” as that term is defined in Rule 501(a) of Regulation D under the Securities Act. Each TCP Holder has sufficient knowledge and experience in financial and business matters so as to be capable of evaluating the merits and risks of its investment in the Conversion Shares and is capable of bearing the economic risks of such investment. Each TCP Holder understands that its investment in the Conversion Shares involves a significant degree of risk.

Section 2.3 Sales or Transfer. Each TCP Holder understands that the sale or re-sale of the Conversion Shares has not been and is not being registered under the Securities Act or any applicable state securities laws, and that the Conversion Shares may not be sold or otherwise transferred unless (a) the Conversion Shares are sold or transferred pursuant to an effective registration statement under the Securities Act and applicable state securities laws, (b) such TCP

2

Holder shall have delivered to the Company an opinion of counsel (which opinion shall be in form, substance and scope customary for opinions of counsel in comparable transactions) to the effect that the Conversion Shares to be sold or transferred may be sold or transferred pursuant to an exemption from such registration, or (c) the Conversion Shares are sold pursuant to Rule 144 under the Securities Act.

Section 2.4 Stockholder Lock-Up Agreement. The TCP Holders acknowledge and understand that under the terms of the Stockholder Lock-Up Agreement they are agreeing to, among other things, refrain from offering, selling, issuing, contracting to sell, pledging, or otherwise disposing of, directly or indirectly, the Conversion Shares for the period specified therein.

Section 2.5 Authorization. The execution, delivery and performance of this Agreement and the TCP Third Lien Notes Conversion are within the TCP Holders’ corporate, partnership or limited liability company, as applicable, powers and have been duly and validly authorized by all requisite corporate, partnership or limited liability company, as applicable, action.

Section 2.6 Valid Existence. Each TCP Holder is an entity duly organized, validly existing and in good standing under the laws of its jurisdiction of formation.

Section 2.7 Binding Agreement. This Agreement has been duly executed and delivered by each TCP Holder, and it constitutes a valid and binding agreement of such TCP Holder.

Section 2.8 Consents; No Violations. Neither the execution, delivery or performance by the TCP Holders of this Agreement nor the consummation of the conversion contemplated hereby shall (a) conflict with, or result in a breach or a violation of, any provision of the certificate of incorporation, bylaws or other organizational documents of any TCP Holder, (b) constitute, with or without notice or the passage of time or both, a breach, violation or default, create any lien or charge, or give rise to any right of termination, modification, cancellation, prepayment, suspension, limitation, revocation or acceleration, under any law, or any provision of any agreement or other instrument to which such TCP Holder is a party or pursuant to which such TCP Holder or any of its assets or properties is subject, except for breaches, violations, defaults, liens or charges, or rights of termination, modification, cancellation, prepayment, suspension, limitation, revocation or acceleration, which, individually or in the aggregate, would not materially adversely affect such TCP Holder’s ability to consummate the transactions contemplated by this Agreement, or (c) require any consents, approvals and filings on the part of such TCP Holder, from or with any governmental entity except for the consents, approvals and filings which, if not made or obtained by such TCP Holder, would not materially adversely affect such TCP Holder’s ability to consummate the transactions contemplated by this Agreement.

3

Section 2.9 Restrictive Legends. The TCP Holders acknowledge that the Conversion Shares shall bear a restrictive legend substantially in the following form:

THE SECURITIES REPRESENTED BY THIS CERTIFICATE HAVE NOT BEEN REGISTERED UNDER THE SECURITIES ACT OF 1933, AS AMENDED (THE “SECURITIES ACT”). THE SECURITIES HAVE BEEN ACQUIRED FOR INVESTMENT PURPOSES ONLY AND MAY NOT BE OFFERED, SOLD, PLEDGED OR OTHERWISE TRANSFERRED EXCEPT PURSUANT TO (A) AN EFFECTIVE REGISTRATION STATEMENT FOR THE SECURITIES UNDER THE SECURITIES ACT AND ANY APPLICABLE STATE SECURITIES LAW, (B) AN OPINION OF COUNSEL, IN FORM, SUBSTANCE AND SCOPE REASONABLY ACCEPTABLE TO THE COMPANY, THAT REGISTRATION IS NOT REQUIRED UNDER THE SECURITIES ACT OR ANY APPLICABLE STATE SECURITIES LAW OR (C) RULE 144 UNDER THE SECURITIES ACT.

ARTICLE III

REPRESENTATIONS AND WARRANTIES OF PARENT AND COMPANY

Parent and Company each represent and warrant to the TCP Holders as follows as of the Closing Date:

Section 3.1 Organization, Standing, etc. Parent and each of its subsidiaries is a corporation duly organized and validly existing and in good standing under the laws of the jurisdiction in which it is incorporated, with all corporate power and authority to own, lease and operate its properties and to conduct its business as currently owned, leased, operated and conducted.

Section 3.2 Issuance of Conversion Shares. Upon issuance by Parent, the Conversion Shares will be validly issued, fully paid and non-assessable, free and clear of all liens and encumbrances and not subject to any preemptive rights, other than any of the foregoing resulting solely from action by the holders of the Conversion Shares.

Section 3.3 Corporate Power; Binding Agreement. Parent and the Company have all requisite corporate power and authority to enter into, execute, deliver and perform their obligations under this Agreement and to consummate the transactions contemplated hereby. This Agreement has been duly authorized, executed and delivered by Parent and the Company, and, assuming the due authorization, execution and delivery thereof by the TCP Holders, constitutes the legal, valid and binding obligation of Parent and the Company, enforceable against Parent and the Company in accordance with its terms, except as the enforcement thereof may be limited by bankruptcy, insolvency and other similar laws affecting the enforcement of creditors’ rights generally and except as enforcement thereof is subject to general principles of equity.

Section 3.4 Consents; No Violations. Neither the execution, delivery or performance by Parent and Company of this Agreement nor the consummation of the transactions contemplated hereby will (a) conflict with, or result in a breach or a violation of, any

4

provision of the certificate of incorporation or bylaws of Parent or the Company, (b) constitute, with or without notice or the passage of time or both, a breach, violation or default, create any lien or charge, or give rise to any right of termination, modification, cancellation, prepayment, suspension, limitation, revocation or acceleration, under any law, or any provision of any agreement or other instrument to which Parent or any of its subsidiaries is a party or pursuant to which any of the assets or properties of Parent or any of its subsidiaries is subject, except for breaches, violations, defaults, liens or charges, or rights of termination, modification, cancellation, prepayment, suspension, limitation, revocation or acceleration, which, individually or in the aggregate, would not materially adversely affect Parent’s or the Company’s ability to consummate the transactions contemplated by this Agreement, or (c) require any consents, approvals and filings on the part of Parent or the Company on or before the Closing Date from or with any governmental entity, except for such consents, approvals and filings which, if not made or obtained by Parent or the Company, would not materially adversely affect the ability of Parent and the Company to consummate the transactions contemplated by this Agreement.

ARTICLE IV

MISCELLANEOUS

Section 4.1 Transfer Taxes. All transfer, documentary, sales, use, stamp, registration, real estate transfer or gains and stock transfer taxes incurred in connection with this Agreement and the transactions contemplated hereby shall be borne by the Company.

Section 4.2 Severability. Whenever possible, each provision of this Agreement shall be interpreted in such manner as to be effective and valid under applicable law, but if any provision of this Agreement is held to be invalid or unenforceable in any respect, such invalidity or unenforceability shall not render invalid or unenforceable any other provision of this Agreement.

Section 4.3 Survival of Representations and Warranties. All representations and warranties set forth in this Agreement or in any writing delivered by any party in connection herewith shall survive the transactions contemplated by this Agreement to be consummated on the Closing Date (regardless of any investigation, inquiry, or examination made by any party or on its behalf or any knowledge of any party or the acceptance by any party of any certificate or opinion) for a period of one year following the Closing Date.

Section 4.4 Enforcement. The parties hereto agree that (a) irreparable damage would occur in the event that any of the provisions of this Agreement were not performed in accordance with their specific intent or were otherwise breached and (b) the parties shall be entitled to an injunction or injunctions to prevent or cure breaches of the provisions of this Agreement and to enforce specifically the terms and provisions hereof, in addition to any other remedy to which they may be entitled by law or equity.

Section 4.5 Successors and Assigns. Except as otherwise expressly provided herein, (a) all covenants and agreements contained in this Agreement by or on behalf of any of the parties hereto shall bind and inure to the benefit of the respective successors, assigns, heirs

5

and legal representatives of the parties hereto, whether so expressed or not, and (b) no party may assign or delegate all or any portion of its rights, obligations or liabilities under this Agreement without the prior written consent of each other party to this Agreement.

Section 4.6 Entire Agreement. This Agreement (including the Exhibits and Schedule hereto) constitute the full and entire understanding and agreement between the parties with regard to the subject matter 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.

Section 4.7 Notices. All notices, demands, requests, consents or other communications to be given or delivered under or by reason of the provisions of this Agreement shall be in writing and shall be deemed to have been given (a) when delivered personally to the recipient, (b) when telecopied to the recipient (with hard copy sent to the recipient by reputable overnight courier service (charges prepaid) that same day) if telecopied before 5:00 p.m. New York City time on a business day, and otherwise on the next business day, (c) one business day after being sent to the recipient by reputable overnight courier service (charges prepaid) or (d) on the first business day that is at least five days after the date of deposit thereof in the United States mails for delivery by certified mail. Such notices, demands, requests, consents and other communications shall be sent to the following persons at the following addresses:

ITC^DeltaCom, Inc.

7037 Old Madison Pike

Huntsville, Alabama 35806

Telecopy No.: (256) 382-3936

Attention: J. Thomas Mullis, Esq.

  Senior Vice President–Legal and Regulatory

With a copy to:

Skadden, Arps, Slate, Meagher & Flom LLP

Four Times Square

New York, NY 10036

Attention: J. Gregory Milmoe

Facsimile: (917)  ###-###-####

and

Hogan & Hartson LLP

8300 Greensboro Drive, Suite 1100

McLean, VA 22102

Attention: Richard J. Parrino

Facsimile: (703)  ###-###-####

6

Tennenbaum Capital Partners, LLC

2951 28^th Street, Suite 1000

Santa Monica, CA 90405

Attention: Michael Leitner and general counsel

Facsimile: (310)  ###-###-####

With a copy to:

Milbank, Tweed, Hadley & McCloy LLP

601 South Figueroa, 30^th Floor

Lost Angeles, CA 90017

Telecopy No.: (213)  ###-###-####

Attention: Melainie K. Mansfield

or to such other address or to the attention of such other person as the recipient party has specified by prior written notice to the sending party.

Section 4.8 Amendments; Waivers. The provisions of this Agreement, including the provisions of this sentence, may not be amended, modified or supplemented, and waivers or consents to departures from the provisions hereof may not be given without the written consent thereto of Parent, the Company, and the TCP Holders. Notwithstanding the foregoing, any such amendment, modification, supplement, waiver or consent with respect to a matter that relates exclusively to the rights or obligations of a particular TCP Holder and that does not directly or indirectly affect the rights or obligations of any other TCP Holders, may be entered into or given solely by Parent, the Company and such affected TCP Holder; provided, however, that the provisions of this sentence may not be amended, modified or supplemented, and no waiver or consent to departure from such provisions may be given, except in accordance with the provisions of the immediately preceding sentence.

Section 4.9 Counterparts. This Agreement may be executed simultaneously in two or more counterparts, any one of which need not contain the signatures of more than one party, but all such counterparts taken together shall constitute one and the same Agreement.

Section 4.10 Headings. The descriptive headings of this Agreement are inserted for convenience only and do not constitute a substantive part of this Agreement.

Section 4.11 Governing Law. This Agreement shall be governed in all respects, including validity, interpretation and effect, by the laws of the State of Delaware applicable to contracts executed and to be performed wholly within such state.

Section 4.12 Exclusive Jurisdiction; Venue. Any process against the Company, Parent or a TCP Holder in, or in connection with, any suit, action or proceeding arising out of or relating to this Agreement or the transactions contemplated hereby, may be served personally or by certified mail pursuant to the notice provision set forth in Section 4.7 with the same effect as

7

though served on it personally. Each of the parties hereto hereby irrevocably submits in any suit, action or proceeding by the parties hereto arising out of or relating to this Agreement or any of the transactions contemplated hereby, to the exclusive jurisdiction and venue of the federal and state courts of the State of Delaware and irrevocably waives any and all objections to exclusive jurisdiction and review of venue that any such party may have under the laws of the State of Delaware or the United States. Without limiting the other remedies, this Agreement shall be enforceable by specific performance.

Section 4.13 Waiver of Jury Trial. Parent, the Company and the TCP Holders hereby waive any right they may have to a trial by jury in respect of any action, proceeding or litigation directly or indirectly arising out of, under or in connection with this Agreement.

Section 4.14 Delivery by Facsimile. This Agreement and each other agreement or instrument entered into in connection herewith or contemplated hereby, and any amendments hereto or thereto, to the extent signed and delivered by means of a facsimile machine, shall be treated in all manner and respects as an original agreement or instrument and shall be considered to have the same binding legal effect as if it were the original signed version thereof delivered in person. At the request of any party hereto or to any such agreement or instrument, each other party hereto or thereto shall re-execute original forms thereof and deliver them to all other parties. No party hereto or to any such agreement or instrument shall raise the use of a facsimile machine to deliver a signature or the fact that any signature or agreement or instrument was transmitted or communicated through the use of a facsimile machine as a defense to the formation or enforceability of a contract, and each such party forever waives any such defense.

[Signatures on Following Page]

8

IN WITNESS WHEREOF, the Company and the TCP Holders have caused this Agreement to be duly executed as of the date first written above.