EXCHANGE AGREEMENT

Exhibit 10.6

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 each of the persons or entities listed on the signature pages hereto under the heading “WCAS Holders” (individually, a “WCAS Holder” and collectively, the “WCAS Holders”).

RECITALS

WHEREAS, Parent, the Company, certain subsidiary guarantors of Parent, certain banks, financial institutions and other institutional lenders (including the WCAS 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 WCAS 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 corporate structure as described in Exhibit A annexed hereto (the “Recapitalization”); and

WHEREAS, on June 8, 2007, Welsh, Carson, Anderson & Stowe VIII, L.P., entered into a commitment letter whereby it confirmed, among other things, its intention to exchange or cause its affiliated investment funds to exchange $23.5 million principal amount of Third Lien Notes (the “WCAS 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 WCAS Holders agree to exchange the WCAS Third Lien Notes for Common Stock, and the Company agrees to issue to the WCAS Holders shares of Common Stock in exchange for the WCAS 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 WCAS Holders hereby agree to exchange their WCAS Third Lien Notes for, and Parent hereby agrees to issue and deliver to the WCAS Holders in exchange for such Notes, a total of 7,757,524 shares of Common Stock (the “WCAS Third Lien Notes Conversion”). Schedule 1 hereto lists, as the date of this Agreement, (i) each WCAS Holder, (ii) the amount of WCAS Third Lien Notes held by each WCAS Holder as of the Closing Date, as reflected in the Company’s books and records, (iii) the total amount of WCAS Third Lien Notes that will be exchanged, (iv) the amount of cash to be received by each WCAS 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 WCAS Holder upon effectiveness of the WCAS Third Lien Notes Conversion (the “Conversion Shares”). The WCAS Third Lien Notes Conversion will be effective, and the WCAS 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 WCAS Holder shall tender to the Company for cancellation all WCAS Third Lien Notes held by such WCAS 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 WCAS Holder a share certificate or certificates, each registered in the name of such WCAS Holder, representing the Conversion Shares.

ARTICLE II

REPRESENTATIONS AND WARRANTIES OF THE WCAS HOLDERS

As of the Closing Date, each WCAS Holder, severally and not jointly, represents and warrants to Parent and the Company, as follows:

Section 2.1. Acquisition for Investment. Such WCAS 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, such WCAS 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. Such WCAS Holder is an “accredited investor,” as that term is defined in Rule 501(a) of Regulation D under the Securities Act. Such WCAS Holder has sufficient knowledge and experience in financial and business matters so as to

2

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. Such WCAS Holder understands that its investment in the Conversion Shares involves a significant degree of risk.

Section 2.3 Sales or Transfer. Such WCAS 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 WCAS 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. Such WCAS Holder, if a party to the Stockholder Lock-Up Agreement, acknowledges and understands that the Conversion Shares are subject to the Stockholder Lock-Up Agreement under the terms of which it is 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. To the extent such WCAS Holder is an entity, the execution, delivery and performance of this Agreement and the WCAS Third Lien Notes Conversion are within such WCAS Holder’s 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. To the extent it is an entity, such WCAS Holder is 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 such WCAS Holder, and it constitutes a valid and binding agreement of such WCAS Holder.

Section 2.8 Consents; No Violations. Neither the execution, delivery or performance by such WCAS 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 such WCAS Holder, where applicable, (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 WCAS Holder is a party or pursuant to which such WCAS 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 WCAS Holder’s ability to

3

consummate the transactions contemplated by this Agreement, or (c) require any consents, approvals and filings on the part of such WCAS Holder, from or with any governmental entity except for the consents, approvals and filings which, if not made or obtained by such WCAS Holder, would not materially adversely affect such WCAS Holder’s ability to consummate the transactions contemplated by this Agreement.

Section 2.9 Restrictive Legends. Such WCAS Holder acknowledges 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.

The conditions to any offer, sale, pledge or other transfer of the Conversion Shares as set forth in the legend above are incorporated in, and form a part of, this Agreement. The legend set forth above shall be removed and the Company shall issue a certificate representing any Conversion Share without such legend to the holder of such Conversion Share upon which it is stamped, if, unless otherwise required by state securities laws, (i) such Conversion Share is sold pursuant to an effective registration statement under the Securities Act, (ii) such holder shall have delivered to the Company evidence reasonably satisfactory to the Company indicating that such Conversion Share may be sold or transferred pursuant to an exemption from registration under the Securities Act or (iii) such holder provides the Company with reasonable assurances that such Conversion Share and all other Conversion Shares then held by such holder may be sold pursuant to Rule 144(k) under the Securities Act or pursuant to Rule 144 under the Securities Act within any three-month period.

ARTICLE III

REPRESENTATIONS AND WARRANTIES OF PARENT AND COMPANY

Parent and Company, jointly and severally, each represent and warrant to the WCAS 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

4

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 Capital Stock. All of the issued shares of capital stock of Parent have been duly and validly authorized and issued and are fully paid and non-assessable. There are no anti-dilution or price adjustment provisions contained in any security issued by Parent (or in any agreement providing rights to security holders) that will be triggered by the issuance of the Conversion Shares.

Section 3.3 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. Moreover, the Conversion Shares issued to the WCAS Holders constitute Registrable Securities under the Registration Rights Agreement, dated as of October 6, 2003, as amended, among Parent and the WCAS Securityholders listed on the signature pages thereof.

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 WCAS 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 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.

5

ARTICLE IV

WCAS REPRESENTATIVE

The WCAS Holders hereby appoint Welsh, Carson, Anderson & Stowe VIII, L.P. as the WCAS Holders’ exclusive agent to act on the WCAS Holders’ behalf with respect to the matters specified in this Article IV. Such representative, or such other representative as the WCAS Holders may appoint from time to time to replace Welsh, Carson, Anderson & Stowe VIII, L.P., is hereinafter referred to as the “WCAS Representative.” The WCAS Representative shall take any and all actions which the WCAS Representative believes are necessary or appropriate under this Agreement for and on behalf of the WCAS Holders as fully as if the WCAS Holders were acting on their own behalf, including, without limitation, making the deliveries referred to in Section 1.2 and taking any and all other actions specified in or contemplated by this Agreement to be taken by the WCAS Holders prior to, on or after the Closing Date, receiving notice of and defending any claims pursuant to this Agreement, giving notice of and asserting any claims pursuant to this Agreement, consenting to, compromising or settling claims made pursuant to this Agreement, and engaging counsel, accountants or other representatives in connection with the foregoing matters. Parent and the Company shall have the right to rely upon all actions taken or omitted to be taken by the WCAS Representative pursuant to this Agreement, all of which actions or omissions shall be legally binding upon each of the WCAS Holders.

ARTICLE V

MISCELLANEOUS

Section 5.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 5.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 5.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.

6

Section 5.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 seek 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 5.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 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; provided, that any such consent required to be given by the WCAS Holders shall be effective if given by the WCAS Representative.

Section 5.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 5.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

7

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)  ###-###-####

Welsh, Carson, Anderson & Stowe

320 Park Avenue

Suite 2500

New York, New York 10022

Telecopy No.: (212) 893-9548

Attention: Thomas E. McInerney

With a copy to:

Davis Polk & Wardwell

450 Lexington Avenue

New York, New York 10017

Telecopy No.: (212) 450-3800

Attention: Carole Schiffman

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 5.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 WCAS Representative. 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 WCAS Holder and that does not directly or indirectly affect the rights or obligations of any other WCAS Holders, may be entered into or given solely by Parent, the Company and such affected WCAS 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.

8

Section 5.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 5.10 Headings. The descriptive headings of this Agreement are inserted for convenience only and do not constitute a substantive part of this Agreement.

Section 5.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 5.12 Exclusive Jurisdiction; Venue. Any process against the Company, Parent or a WCAS 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 5.7 with the same effect as 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 5.13 Waiver of Jury Trial. Parent, the Company and the WCAS 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 5.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.

[The remainder of this page is intentionally left blank]

9

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