AMENDMENT NO. 1 TO WARRANT AGREEMENT

Exhibit 4.2

AMENDMENT NO. 1 TO WARRANT AGREEMENT

THIS AMENDMENT NO. 1 TO WARRANT AGREEMENT, dated as of July 26, 2005 (this “Amendment”), is between ITC^DeltaCom, Inc., a Delaware corporation (the “Company”), and Mellon Investor Services LLC, a New Jersey limited liability company, as warrant agent (the “Warrant Agent”).

W I T N E S S E T H:

WHEREAS, the Company and the Warrant Agent are parties to a Warrant Agreement, dated as of March 29, 2005 (the “Agreement”), pursuant to which the Company has issued and delivered 20,000,000 warrants;

WHEREAS, the Holders (as such term is defined in the Agreement) of a majority of such warrants outstanding as of the date hereof have consented in writing to this Amendment in accordance with Section 12(a) of the Agreement; and

WHEREAS, the Company wishes to amend the Agreement pursuant to such consent, as hereinafter provided;

NOW, THEREFORE, in consideration of the promises and the mutual agreements herein set forth, the parties hereby agree as follows:

SECTION 1. CAPITALIZED TERMS.

Capitalized terms used in this Amendment and not defined herein have the meanings given to such terms in the Agreement.

SECTION 2. AMENDMENT TO SECTION 3 OF AGREEMENT.

Subparagraph (i) of Section 3(i) of the Agreement is hereby amended by deleting existing subparagraph (i) of Section 3(i) in its entirety and by substituting therefor a new subparagraph (i) of Section 3(i), which shall read in its entirety as follows:

(i) any taking by the Company of a record of the holders of any class of securities of the Company for the purpose of determining the holders thereof who are entitled to receive any dividend or other distribution, or any right to subscribe for, purchase or otherwise acquire any shares of Capital Stock of any class or any other securities or property, or to receive any other right, other than, in each case, (A) a regular quarterly or other periodic dividend publicly announced by the Company or provided for in the instrument governing such class of securities (including, without limitation, dividends payable on the Series A Preferred Stock pursuant to the Series A Certificate of Designation as in effect on or prior to the Amendment Date, on the Series B Preferred Stock pursuant to the Series B Certificate of Designation as in effect on or prior to the Amendment Date, or on the Series C Preferred Stock pursuant to the Series C Certificate of Designation), (B) any other issuance of the Series A Preferred Stock after the Issue Date pursuant to the Series A Certificate of Designation as in effect on or prior to the Amendment Date,

any other issuance of the Series B Preferred Stock after the Issue Date pursuant to the Series B Certificate of Designation as in effect on or prior to the Amendment Date, or any other issuance of the Series C Preferred Stock after the Issue Date pursuant to the Series C Certificate of Designation or (C) a regular quarterly or other periodic payment of interest in cash or securities on, or such payment of interest effectuated by an increase in the amount of, any issue of the Company’s indebtedness in accordance with the instrument governing such indebtedness, or

SECTION 3. AMENDMENT TO SECTION 7 OF AGREEMENT.

(a) Section 7(b)(v) of the Agreement is hereby amended by deleting the penultimate sentence of existing Section 7(b)(v) in its entirety and by substituting therefor a new penultimate sentence of Section 7(b)(v), which shall read in its entirety as follows:

The determination of such Independent Appraiser with respect to the fair value of such consideration, or, if the Company is not required to retain an Independent Appraiser pursuant to this Section 7(b)(v), but retains an Independent Appraiser pursuant to the Series A Certificate of Designation, the Series B Certificate of Designation, the Series C Certificate of Designation or any Other Warrant Agreement to determine the fair value of such consideration for purposes of the Series A Certificate of Designation, the Series B Certificate of Designation, the Series C Certificate of Designation or such Other Warrant Agreement, as the case may be, the determination of such other Independent Appraiser with respect to the fair value of such consideration shall be final and binding upon the Company, the Warrant Agent and the Holders of the Warrants.

(b) Section 7(c) of the Agreement is hereby amended by deleting existing Section 7(c) in its entirety and by substituting therefor a new Section 7(c), which shall read in its entirety as follows:

No adjustment of the Exercise Price shall be made pursuant to Section 7(a) or 7(b) upon the issuance, sale, grant, exercise, conversion, exchange, reclassification, redemption or other retirement of any of the following securities after the Issue Date:

(i) the Merger Common Stock;

(ii) the Series A Preferred Stock, including the Series A Preferred Stock issuable as dividends on the Series A Preferred Stock or otherwise issuable after the Issue Date, issuable pursuant to the Series A Certificate of Designation as in effect on or prior to the Amendment Date, or any shares of Common Stock or other securities issuable or payable upon conversion of the Series A Preferred Stock pursuant to the Series A Certificate of Designation as in effect on or prior to the Amendment Date;

(iii) any shares of Common Stock, Options or Convertible Securities issuable as a dividend or distribution on the Series A Preferred Stock in accordance with the Series A Certificate of Designation as in effect on or prior to the Amendment Date or any shares of Common Stock issuable or payable upon exercise of any such Options or upon conversion or exchange of any such Convertible Securities;

2

(iv) the Series B Preferred Stock, including the Series B Preferred Stock issuable as dividends on the Series B Preferred Stock or otherwise issuable after the Issue Date, issuable pursuant to the Series B Certificate of Designation as in effect on or prior to the Amendment Date, or any shares of Common Stock or other securities issuable or payable upon conversion of the Series B Preferred Stock pursuant to the Series B Certificate of Designation as in effect on or prior to the Amendment Date;

(v) any shares of Common Stock, Options or Convertible Securities issuable as a dividend or distribution on the Series B Preferred Stock in accordance with the Series B Certificate of Designation as in effect on or prior to the Amendment Date, or any shares of Common Stock issuable or payable upon exercise of any such Options or upon conversion or exchange of any such Convertible Securities;

(vi) the Series C Preferred Stock, including the Series C Preferred Stock issuable as dividends on the Series C Preferred Stock or otherwise issuable after the Issue Date, issuable pursuant to the Series C Certificate of Designation, or any shares of Common Stock or other securities issuable or payable upon conversion of the Series C Preferred Stock pursuant to the Series C Certificate of Designation;

(vii) any shares of Common Stock, Options or Convertible Securities issuable as a dividend or distribution on the Series C Preferred Stock in accordance with the Series C Certificate of Designation, or any shares of Common Stock issuable or payable upon exercise of any such Options or upon conversion or exchange of any such Convertible Securities;

(viii) the Series A Warrants or any shares of Common Stock or other securities issuable or payable upon exercise or conversion of the Series A Warrants;

(ix) the Series B Warrants or any shares of Common Stock or other securities issuable or payable upon exercise or conversion of the Series B Warrants;

(x) the Warrants or any shares of Common Stock or other securities issuable or payable upon exercise or conversion of the Warrants;

(xi) the Series D Warrants or any shares of Series C Preferred Stock, Common Stock or other securities issuable or payable upon exercise or conversion of the Series D Warrants;

(xii) any shares of Common Stock, Options or Convertible Securities issuable under (A) the Existing Benefit Plan as in effect on the Amendment Date or (B) the Existing Benefit Plan as amended after the Amendment Date and any Benefit Plan which becomes effective after the Amendment Date, provided that any such amendment to the Existing Benefit Plan or the effectiveness of any such Benefit Plan is approved by the Board of Directors or by the compensation committee or other authorized committee of the Board of Directors (in either case with the affirmative vote or consent of the Series B Directors, if any, in each case whether or not serving on any such committee), or any shares of Common Stock issuable or payable upon exercise of any such Options or upon conversion or exchange of any such Convertible Securities;

3

(xiii) any shares of Common Stock issued or deemed to have been issued in a transaction for which an adjustment of the Exercise Price is required pursuant to Section 7(d);

(xiv) any transaction referred to in Section 7(e);

(xv) any shares of Common Stock, Options or Convertible Securities issued in connection with the acquisition of all or part of another business or company, whether by merger, consolidation or otherwise, which is approved by the Board of Directors or by an authorized committee of the Board of Directors (in either case with the affirmative vote or consent of the Series B Directors, if any, in each case whether or not serving on any such committee), any shares of Common Stock issuable or payable upon exercise of any such Options or upon conversion or exchange of any such Convertible Securities, or any shares of Common Stock, payment-in-kind securities or other securities issuable as a dividend or distribution on any such shares of Common Stock, Options or Convertible Securities;

(xvi) any shares of Common Stock, Options or Convertible Securities issued pursuant to or as provided in the Executive Employment Agreements, or any shares of Common Stock or other securities issuable or payable upon exercise of any such Options or upon conversion or exchange of any such Convertible Securities; or

(xvii) any shares of Common Stock, Options or Convertible Securities issued or deemed to have been issued in any transaction not referred to in any of subparagraphs (i) through (xvi) of this Section 7(c) if the Holders of a majority of the Warrants outstanding at the time of such written consent have agreed in a written consent that any such issuance or deemed issuance pursuant to any such transaction shall not require an adjustment of the Exercise Price pursuant to Section 7(a) or 7(b).

(c) Section 7(d) of the Agreement is hereby amended by deleting existing Section 7(d) in its entirety and by substituting therefor a new Section 7(d), which shall read in its entirety as follows:

(d) If a date of record should be fixed at any time, whether by the Company or by operation of law, for the subdivision (by any stock split, stock dividend, recapitalization, reorganization, reclassification or otherwise) of the shares of Common Stock acquirable hereunder into a greater number of shares, or for the determination of the holders of Common Stock entitled to receive a dividend or other distribution payable in additional shares of Common Stock, Convertible Securities or Options without payment of any consideration for the additional shares of Common Stock, Convertible Securities or Options (including the additional shares of Common Stock or Convertible Securities issuable upon conversion or exercise of such Options), then, as of such date of record, the Exercise Price in effect immediately prior to such date of record shall be proportionately reduced (with the number of shares of Common Stock or Convertible Securities issuable with respect to Options determined from time to time in the manner provided for deemed issuances or sales of Common Stock in Section 7.2(b)). If such subdivision of the shares of Common Stock or the payment of such dividend or distribution does not thereafter occur, the Exercise Price in effect shall be readjusted to the Exercise Price that would have been in

4

effect if the date of record for such subdivision, dividend or distribution had never been fixed. If a date of record should be fixed at any time, whether by the Company or by operation of law, for the combination (by reverse stock split, recapitalization, reorganization, reclassification or otherwise) of the shares of Common Stock acquirable hereunder into a smaller number of shares of Common Stock, then, as of such date of record, the Exercise Price in effect immediately prior to such date of record shall be proportionately increased. If such combination of the shares of Common Stock does not thereafter occur, the Exercise Price then in effect shall be readjusted to the Exercise Price that would have been in effect if the date of record for such combination had never been fixed.

SECTION 4. AMENDMENT TO SECTION 12 OF AGREEMENT.

Section 12(b) of the Agreement is hereby amended by deleting existing Section 12(b) in its entirety and by substituting therefor a new Section 12(b), which shall read in its entirety as follows:

(b) So long as any Warrants are outstanding and held by the Required Initial Holders, prior to amending the Series A Warrant Agreement, the Series B Warrant Agreement or the Series D Warrant Agreement in such a manner as to provide the Holders of the Series A Warrants, the Series B Warrants or the Series D Warrants, as the case may be, with rights in addition or superior to those provided to the Holders of the Warrants under this Agreement, the Company shall give written notice of any such proposed amendment (the “Proposed Amendment”), which shall include the text of the Proposed Amendment, to the Required Initial Holders (with a copy to the Warrant Agent) and shall offer to the Required Initial Holders to amend this Agreement (subject to any consent requirements imposed by this Agreement) so as to provide the Holders of the Warrants with rights no less favorable than the rights to be provided to the Holders of the Series A Warrants, the Series B Warrants and the Series D Warrants, as the case may be, in the Proposed Amendment. If, within ten Business Days after their receipt of such written notice from the Company, the Required Initial Holders shall give written notice to the Company (with a copy to the Warrant Agent) that they seek to have this Agreement amended to provide the Holders of the Warrants with such rights, the Company shall not amend the Series A Warrant Agreement, the Series B Warrant Agreement or the Series D Warrant Agreement, as the case may be, to provide for such rights unless, concurrently with, or immediately prior to, the effectiveness of the Proposed Amendment, the Company shall amend this Agreement to provide such rights to the Holders of the Warrants. If within the period of ten Business Days described in the immediately preceding sentence, the Required Initial Holders do not so provide notice to the Company that they seek to have this Agreement so amended, or if the Holders of the Warrants do not approve and consent to such an amendment to this Agreement, the Company shall be deemed to have complied with this Section 12(b) with respect to the Proposed Amendment, and the Company shall then have the right to amend the Series A Warrant Agreement, the Series B Warrant Agreement or the Series D Warrant Agreement, as the case may be, as provided in the Proposed Amendment without so amending this Agreement. In no event shall the failure of the Required Initial Holders to seek to have this Agreement amended under this Section 12(b) with respect to any Proposed Amendment affect the applicability of this Section 12(b) with respect to any subsequent Proposed Amendment. Any written notice required to be given by the Company or the Required Initial Holders pursuant to this Section 12(b) shall be given in the manner, and with the effect provided in, Section 3(f).

5

SECTION 5. AMENDMENT TO SECTION 15 OF AGREEMENT.

(a) Section 15 of the Agreement is hereby amended by adding, in the appropriate alphabetical order, the following definitions to such Section 15:

“Amendment Date” means July 26, 2005.

“Executive Employment Agreements” means (i) the Employment Agreement, dated as of February 3, 2005, between the Company and Randall E. Curran, as amended from time to time (provided that no amendment to such Employment Agreement after the Amendment Date shall change the type or increase the amount of securities of the Company issuable thereunder), (ii) the Employment Agreement, dated as of February 21, 2005, between the Company and Richard E. Fish, Jr., as amended from time to time (provided that no amendment to such Employment Agreement after the Amendment Date shall change the type or increase of the amount of securities of the Company issuable thereunder), and (iii) the Employment Agreement, dated as of February 28, 2005, between the Company and James P. O’Brien, as amended from time to time (provided that no amendment to such Employment Agreement after the Amendment Date shall change the type or increase the amount of securities of the Company issuable thereunder).

“Other Warrant Agreement” means any of (i) the Series A Warrant Agreement, (ii) the Series B Warrant Agreement or (iii) the Series D Warrant Agreement.

“Series A Warrant Agreement” means the Warrant Agreement, dated as of October 29, 2002, between the Company and Mellon Investor Services LLC, as Warrant Agent, as amended from time to time (so long as no amendment to such Warrant Agreement after the Amendment Date shall increase the number of warrants issuable pursuant thereto).

“Series B Warrant Agreement” means the Warrant Agreement, dated as of October 6, 2003, between the Company and Mellon Investor Services LLC, as Warrant Agent, as amended from time to time (so long as no amendment to such Warrant Agreement after the Amendment Date shall increase the number of warrants issuable pursuant thereto).

“Series C Certificate of Designation” means the Certificate of Designation of the Powers, Preferences and Relative, Participating, Optional and Other Special Rights of 8% Series C Convertible Redeemable Preferred Stock and Qualifications, Limitations and Restrictions Thereof, as amended from time to time.

“Series C Preferred Stock” means the 8% Series C Convertible Redeemable Preferred Stock of the Company authorized in the Series C Certificate of Designation.

“Series D Warrant Agreement” means the Warrant Agreement, dated as of July 26, 2005, between the Company and Mellon Investor Services LLC, as Warrant Agent, as amended from time to time (so long as no amendment to such Warrant Agreement after the Amendment Date shall increase the number of warrants issuable pursuant thereto).

6

“Series D Warrants” means the warrants to purchase Series C Preferred Stock and Common Stock issued by the Company pursuant to the Series D Warrant Agreement; provided that such warrants have the same exercise expiration date and (subject to adjustments pursuant to antidilution provisions and other exercise price adjustment provisions of the Series D Warrant Agreement) the same exercise price as the warrants initially issued pursuant to the Series D Warrant Agreement.

(b) Section 15 of the Agreement is hereby amended by deleting therefrom the existing definitions of “Common Stock Deemed Outstanding,” “Existing Benefit Plan,” “Series A Certificate of Designation,” “Series A Warrants” and “Series B Certificate of Designation” in their entirety and by substituting therefor, in the appropriate alphabetical order, the following definitions, which shall read in their entirety as follows:

“Common Stock Deemed Outstanding” means, on any date of determination, the number of shares of Common Stock actually outstanding, plus the maximum total number of shares of Common Stock issuable as of the date of such determination upon the exercise of any then outstanding Options (including, without limitation, the Series A Warrants, the Series B Warrants, the Series D Warrants and the Warrants and any Options outstanding under the Existing Benefit Plan or any other Benefit Plan) or issuable as of such date of determination upon conversion or exchange of any then outstanding Convertible Securities (including, without limitation, the Series A Preferred Stock, the Series B Preferred Stock and the Series C Preferred Stock), whether or not such Options or Convertible Securities are actually exercisable, convertible or exchangeable at such time, without duplication.

“Existing Benefit Plan” means each of the ITC^DeltaCom, Inc. Amended and Restated Stock Incentive Plan and the ITC^DeltaCom, Inc. Executive Stock Incentive Plan.

“Series A Certificate of Designation” means the Certificate of Designation of the Powers, Preferences and Relative, Participating, Optional and Other Special Rights of 8% Series A Convertible Redeemable Preferred Stock and Qualifications, Limitations and Restrictions Thereof, as amended from time to time unless otherwise specified in this Agreement.

“Series A Warrants” means the warrants to purchase Common Stock issued by the Company pursuant to the Series A Warrant Agreement; provided that such warrants have the same exercise expiration date and (subject to adjustments pursuant to antidilution provisions of the Series A Warrant Agreement) the same exercise price as the warrants issued pursuant to the Series A Warrant Agreement which are outstanding on the Issue Date.

“Series B Certificate of Designation” means the Certificate of Designation of the Powers, Preferences and Relative, Participating, Optional and Other Special Rights of 8% Series B Convertible Redeemable Preferred Stock and Qualifications, Limitations and Restrictions Thereof, as amended from time to time unless otherwise specified in this Agreement.

7

SECTION 6. EFFECTIVENESS.

This Amendment shall be effective as of the date hereof. From and after the effectiveness of this Amendment, each reference in the Agreement to “this Agreement” shall mean the Agreement as amended by this Amendment. Except as amended by this Amendment, the terms and provisions of the Agreement shall remain unchanged.

SECTION 7. GOVERNING LAW.

This Amendment shall be deemed to be a contract made under the laws of the State of New York and for all purposes shall be construed in accordance with the internal laws of the State of New York, without giving effect to principles of conflict of laws to the extent the application of the laws of another jurisdiction would be required thereby.

[signature page follows]

8

IN WITNESS WHEREOF, the parties hereto have caused this Agreement to be duly executed, as of the day and year first above written.

9