VOTING AGREEMENT

Exhibit 10.1

VOTING AGREEMENT

This VOTING AGREEMENT, dated as of September 8, 2004 (this “Agreement”), is entered into by and among Florida Digital Network, Inc., a Delaware corporation (the “Company”), and each of the undersigned stockholders (each a “Stockholder” and, collectively, the “Stockholders”) of ITC^DeltaCom, Inc., a Delaware corporation (“Parent”).

WHEREAS, pursuant to an Agreement and Plan of Merger, dated as of the date hereof (the “Merger Agreement”), by and among Parent, Boatramp Co., a Delaware corporation and a wholly owned subsidiary of Parent (the “Merger Co.”), the Company and certain stockholders of the Company listed on the signature pages thereof, Merger Co. will be merged with and into the Company (the “Merger”), the separate existence of Merger Co. will cease and the Company will continue as the surviving corporation of the Merger;

WHEREAS, as of the date hereof, the Stockholders are the record and beneficial owners of shares of Parent Common Stock and/or shares of the preferred stock of Parent, par value $0.01 per share, designated as the 8% Series B Convertible Redeemable Preferred Stock;

WHEREAS, approval by the stockholders of Parent of the Merger Agreement and issuance of the Parent Common Stock in the Merger is a condition to the consummation of the Merger; and

WHEREAS, as a condition to its entering into the Merger Agreement, the Company has required that the Stockholders agree, and the Stockholders have agreed, to enter into this Agreement;

NOW, THEREFORE, in consideration of the foregoing and for other good and valuable consideration, the receipt and sufficiency of which hereby are acknowledged, the parties agree as follows:

Section 1. Definitions. Capitalized terms used herein and not otherwise defined herein shall have the meanings given to such terms in the Merger Agreement.

Section 2. Agreement to Vote.

(a) Each Stockholder hereby agrees to attend the Parent Stockholders Meeting, in person or by proxy, and to vote (or to cause to be voted) all shares of Parent capital stock set forth opposite the name of such Stockholder in Schedule I hereto, and any other voting securities of Parent, whether issued before or after the date of this Agreement, that such Stockholder has the right to vote (such shares of Parent capital stock and other voting securities of such Stockholder, the “Subject Shares”), as follows:

Such agreement of each Stockholder to vote with respect to the foregoing matters (collectively, the “Stockholder Meeting Proposals”) shall also apply to any adjournment or adjournments of the Parent Stockholders Meeting and to any other meeting of Parent’s stockholders at which any item of business referred to in the preceding sentence is presented for approval.

(b) Each Stockholder agrees to grant to the persons designated by Parent’s Board of Directors, as the attorneys-in-fact or proxies of Parent’s Board of Directors with respect to the Parent Stockholders Meeting and any other meeting of Parent’s stockholders referred to in Section 2(a), a written proxy, which shall be substantially in such form as Parent shall solicit from other stockholders of Parent, to vote such Stockholder’s Subject Shares with respect to the Stockholder Meeting Proposals in the manner specified in Section 2(a).

(c) To the extent inconsistent with the foregoing provisions of this Section 2, each Stockholder hereby revokes any and all previous proxies with respect to such Stockholder’s Subject Shares.

Section 3. Further Assurances; Restrictions on Transfer.

(a) Each party hereto shall execute and deliver such additional instruments and other documents and shall take such further actions as may be necessary or appropriate to effectuate, carry out and comply with all of its obligations under this Agreement. No Stockholder shall enter into any agreement or arrangement (or alter, amend or terminate any existing agreement or arrangement) if such action would impair the ability of such Stockholder to effectuate, carry out or comply with all of its obligations under this Agreement.

(b) Prior to the Effective Time, each Stockholder agrees that it shall not Transfer (or agree to Transfer) any of its Subject Shares. As used in this Section 3(b), “Transfer” means, with respect to any security, the direct or indirect assignment, sale, transfer, tender, pledge, hypothecation, or the grant, creation or sufferage of a lien or encumbrance in or upon, or the gift, placement in trust, or the constructive sale or other disposition of such security (including transfers by testamentary or intestate succession or otherwise by operation of law) or any right, title or interest therein (including, but not limited to, any right or power to vote to which the holder thereof may be entitled, whether such right or power is granted by proxy or otherwise), or the record or beneficial ownership thereof, the offer to make such a sale, transfer, constructive sale or other disposition, and each agreement, arrangement or understanding, whether or not in writing, to effect any of the foregoing. The term “constructive sale” means a short sale with respect to such security, entering into or acquiring an offsetting derivative contract with respect to such security, entering into or acquiring a futures or forward contract to deliver such security or entering into any other hedging or other derivative transaction that has the effect of materially changing the economic benefits and risks of ownership.

- 2 -

Section 4. Authorization; Binding Obligation; Ownership. Each Stockholder (other than any Stockholder that is a natural person) has all necessary corporate, partnership or limited liability company power and authority to execute and deliver this Agreement and to perform its obligations hereunder. The execution, delivery and performance by each Stockholder (other than any Stockholder that is a natural person) of this Agreement are within such Stockholder’s powers and have been duly and validly authorized by all necessary corporate, partnership or limited liability company action. This Agreement has been duly and validly executed and delivered by each Stockholder. Assuming this Agreement constitutes a legal, valid and binding agreement of the other parties hereto, this Agreement constitutes a legal, valid and binding agreement of each Stockholder, enforceable against such Stockholder in accordance with its terms, except as such enforcement is limited by bankruptcy, insolvency and other similar laws affecting the enforcement of creditors’ rights generally and for limitations imposed by general principles of equity. Each Stockholder is the record and beneficial owner of the number of Subject Shares set forth opposite the name of such Stockholder on Schedule I hereto and, as of the date hereof, such Subject Shares are the only voting securities of Parent owned of record by such Stockholder.

Section 5. Non-contravention. The execution, delivery and performance by each Stockholder of this Agreement do not and shall not (a) if such Stockholder is not a natural person, contravene or conflict with the organizational documents of such Stockholder, (b) contravene or conflict with or constitute a violation of any provision of any law, rule, regulation, judgment, writ, injunction, order or decree of any court or governmental authority binding upon or applicable to such Stockholder or any of its properties or assets, or (c) contravene or constitute a default under any provision of any agreement, contract or other instrument binding upon such Stockholder or any of its properties or assets.

Section 6. Effectiveness and Termination. This Agreement shall become effective upon execution and delivery of the Merger Agreement. If the Merger Agreement shall be terminated in accordance with its terms, this Agreement shall automatically terminate and be of no further force or effect. Upon such termination of this Agreement, except for any rights any party may have in respect of any breach by any other party of its obligations hereunder, none of the parties hereto shall have any further obligation or liability hereunder.

Section 7. Miscellaneous.

(a) Notices, Etc. All notices, requests, demands or other communications required by or otherwise with respect to this Agreement shall be in writing and shall be deemed to have been duly given to any party when delivered personally (by courier service or otherwise), when delivered by telecopy and confirmed by return telecopy, or seven days after being mailed by first-class mail, postage prepaid in each case to the applicable addressed set forth below:

If to the Company:

Florida Digital Network, Inc.

2301 Lucien Way

Suite 200

Maitland, Florida 32757

- 3 -

with copies (which shall not constitute notice) to:

Foley & Lardner LLP

P. O. Box 3391

Tampa, Florida ###-###-####

Edwards & Angell, LLP

101 Federal Street

Boston, Massachusetts 02110-1800

If to any Stockholder:

Thomas E. McInerney

320 Park Avenue

Suite 2500

New York, New York 10022

with a copy (which shall not constitute notice) to:

Davis Polk & Wardwell

450 Lexington Avenue

New York, New York 10017

(b) Amendments, Waivers, Etc. This Agreement may not be amended, changed, supplemented, waived or otherwise modified or terminated except by an instrument in writing signed by the Company and each Stockholder.

(c) Successors and Assigns. This Agreement shall be binding upon and shall inure to the benefit of and be enforceable by the parties and their respective successors and assigns, including, without limitation, in the case of any corporate party hereto any corporate successor by merger or otherwise, and in the case of any individual party hereto any trustee, executor, heir, legatee or personal representative succeeding to the ownership of such party’s

- 4 -

Subject Shares. Notwithstanding any transfer of Subject Shares, the transferor thereof shall remain liable for the performance of all of its obligations under this Agreement.

(d) Entire Agreement. This Agreement embodies the entire agreement and understanding among the parties relating to the subject matter hereof and supersedes all prior agreements and understandings relating to such subject matter. There are no representations, warranties or covenants by the parties hereto relating to such subject matter other than those expressly set forth in this Agreement.

(e) Severability. If any term of this Agreement or the application thereof to any party or circumstance shall be held invalid or unenforceable to any extent, the remainder of this Agreement and the application of such term to the other parties or circumstances shall not be affected thereby and shall be enforced to the greatest extent permitted by applicable law, provided, that in such event the parties shall negotiate in good faith in an attempt to agree to another provision (in lieu of the term or application held to be invalid or unenforceable) that will be valid and enforceable and will carry out the parties’ intentions hereunder.

(f) Specific Performance. The parties acknowledge that money damages are not an adequate remedy for violations of this Agreement and that any party may, in its sole discretion, apply to a court of competent jurisdiction for specific performance or injunctive or such other relief as such court may deem just and proper in order to enforce this Agreement or prevent any violation hereof and, to the extent permitted by applicable law, each party waives any objection to the imposition of such relief.

(g) Remedies Cumulative. All rights, powers and remedies provided under this Agreement or otherwise available in respect hereof at law or in equity shall be cumulative and not alternative, and the exercise or beginning of the exercise of any thereof by any party shall not preclude the simultaneous or later exercise of any other such right, power or remedy by such party.

(h) No Waiver. The failure of any party hereto to exercise any right, power or remedy provided under this Agreement or otherwise available in respect hereof at law or in equity, or to insist upon compliance by any other party hereto with its obligations hereunder, and any custom or practice of the parties at variance with the terms hereof, shall not constitute a waiver by such party of its right to exercise any such or other right, power or remedy or to demand such compliance.

(i) No Third-Party Beneficiaries. This Agreement is not intended to be for the benefit of, and shall not be enforceable by, any Person which is not a party hereto.

(j) Jurisdiction. Each party hereby irrevocably submits to the exclusive jurisdiction of the Court of Chancery in the State of Delaware or the United States District Court for the Southern District of New York or any court of the State of New York located in the City of New York in any action, suit or proceeding arising in connection with this Agreement, and agrees that any such action, suit or proceeding shall be brought only in such court (and waives any objection based on forum non conveniens or any other objection to venue therein); provided, however, that such consent to jurisdiction is solely for the purpose referred

- 5 -

to in this Section 7(j) and shall not be deemed to be a general submission to the jurisdiction of such Courts or in the States of Delaware or New York other than for such purposes. EACH PARTY HERETO HEREBY WAIVES ANY RIGHT TO A TRIAL BY JURY IN CONNECTION WITH ANY SUCH ACTION, SUIT OR PROCEEDING.

(k) Governing Law. This Agreement and all disputes hereunder shall be governed by and construed and enforced in accordance with the General Corporation Law of the State of Delaware to the fullest extent possible and otherwise by the internal laws of the State of Delaware without regard to principles of conflicts of law.

(l) Name; Captions; Gender. The name to assigned this Agreement and the section captions used herein are for convenience of reference only and shall not affect the interpretation or construction of any provision of this Agreement. Whenever the context may require, any pronoun used herein shall include the corresponding masculine, feminine or neuter forms.

(m) Counterparts. This Agreement may be executed in any number of counterparts, each of which shall be deemed to be an original, but all of which together shall constitute one instrument. Each counterpart may consist of a number of copies each signed by less than all, but together signed by all, the parties hereto.

(n) Limitation on Liability. No Stockholder shall have any liability hereunder for any actions or omissions of any other Stockholder.

(o) Expenses. The Company and Parent shall each bear its own expenses, and Parent shall bear the reasonable expenses of the Stockholders, incurred in connection with this Agreement and the transactions contemplated hereby.

(p) Stockholder Capacity. Each Stockholder has signed this Agreement solely in its capacity as the beneficial owner of such Stockholder’s Subject Shares, and nothing herein shall limit or affect any actions taken or omitted to be taken by such Stockholder in its capacity as an officer or director of Parent.

(q) Merger Agreement. Each of Parent and the Company agree that prior to the Effective Time it shall not, without the prior written consent of the Stockholders, amend or modify, or grant or receive any waiver under, the Merger Agreement or any other Transaction Agreement.

[Signature pages follow]

- 6 -

IN WITNESS WHEREOF, the parties hereto have duly executed and delivered this Agreement, or have caused this Agreement to be executed and delivered on their behalf, as of the date first above written.

Parent hereby acknowledges and consents to its obligations pursuant to Section 7(o) and 7(q) hereof.

SCHEDULE I