Exhibit 4.1

INTERNET AMERICA, INC.

2004 NON-EMPLOYEE DIRECTOR PLAN

This 2004 Non-Employee Director Stock Option Plan (this “Plan”) is an equity incentive plan for non-employee directors of Internet America, Inc. (the “Company”) and is intended to advance the best interests of the Company, its subsidiaries and its shareholders by providing the Company’s non-employee directors an opportunity to obtain or increase their proprietary interest in the success of the Company and its subsidiaries by becoming owners of the common stock, $0.01 par value, of the Company (the “Stock”) or, in the event that the outstanding shares of common stock are later changed into or exchanged for a different class of stock or securities of the Company or another corporation, that other stock or security. This Plan will be beneficial to the Company and its shareholders since it will allow these directors to have a greater personal financial stake in the Company through the ownership of Stock of the Company, in addition to underscoring their common interest with shareholders in increasing the value of the Company over the long term.

1. Eligibility.

All members of the Company’s Board of Directors who are not current employees of the Company or any of its subsidiaries (“Non-Employee Directors”) are eligible to participate in this Plan.

2. Options.

The term “Option” means an option to purchase shares of Stock granted to a Non-Employee Director pursuant to Section 4 and which is not intended to qualify as an incentive stock option under Section 422 of the Internal Revenue Code of 1986, as amended (the “Code”). Unless otherwise indicated, the term Option includes a “30-Day Option”.

3. Number of Shares Available.

There are hereby reserved for issuance under this Plan an aggregate of 600,000 shares of Stock, which shares may be authorized but unissued shares, treasury shares, or shares purchased on the open market or privately. To the extent any shares of Stock covered by an Option are not delivered to a grantee because the Option is forfeited or canceled, such shares shall not be deemed to have been delivered for purposes of determining the maximum number of shares of Stock available for delivery under this Plan. If the Option Price (as defined in Section 5) of any Option granted under this Plan is satisfied by tendering shares of Stock to the Company (by actual delivery), only the number of shares of Stock issued net of the shares of Stock tendered shall be deemed delivered for purposes of determining the maximum number of shares of Stock available for delivery under this Plan.

4. Initial and Annual Grant of Options.

(a) On the next business day (the “Initial Award Date”) after the later to occur of (i) the date an individual is appointed or elected as a Non-Employee Director of the Company for the first time, or (ii) the date this Plan is adopted by the Board of Directors for those Non-Employee Directors appointed or elected prior to the date of the approval of this Plan, such Non-Employee Director:

1

(A) shall automatically receive the following:

1. an Option to purchase a number of shares of Stock (rounded to the nearest whole share) equal to the lesser of (i) $20,000 divided by the per share fair market value of such Stock on the Initial Award Date or (ii) 30,000 shares; notwithstanding the foregoing, those Non-Employee Directors, appointed or elected prior to the date of the approval of this Plan by the shareholders, shall receive an Option to purchase 30,000 shares of Stock, and

2. a 30-Day Option to purchase a number of shares of Stock equal to the number of shares determined under the foregoing clause (A)(1); and

(B) may, at the discretion of the Board of Directors, receive the following (such new Non-Employee Director shall not participate in the approval by the Board of Directors of any such discretionary award):

1. an Option to purchase up to 50,000 shares of Stock, and

2. a 30-Day Option to purchase a number of shares of Stock equal to the number of shares granted by the Board of Directors under the Option described in the foregoing clause (B)(1), if any.

In the case of a Non-Employee Director who is appointed or elected as the Chairman of the Board for the first time, in addition to Options granted above, if any, such Chairman of the Board shall automatically receive a one-time grant of the following:

1. an Option to purchase a number of shares of Stock (rounded to the nearest whole share) equal to the lesser of (i) $50,000 divided by the per share fair market value of such Stock on the Initial Award Date or (ii) 70,000 shares; notwithstanding the foregoing, that Non-Employee Director appointed or elected as the Chairman of the Board prior to the date of the approval of this Plan by the shareholders, shall receive an Option to purchase 70,000 shares of Stock, and

2. a 30-Day Option to purchase a number of shares of Stock equal to the number of shares determined under the foregoing clause (1) of this sentence.

(b) On the first business day (an “Award Date”) following a Non-Employee Director’s anniversary of election to the Board of Directors, such Non-Employee Director shall automatically receive an Option to purchase a number of shares of Stock (rounded to the nearest whole share) equal to the lesser of (i) $20,000 divided by the per share fair market value of such Stock on the Award Date or (ii) 30,000 shares.

(c) Notwithstanding the foregoing, if, on an Initial Award Date or an Award Date, the Chief Executive Officer or Chief Financial Officer, in consultation with the legal counsel of the Company, determines, in his/her sole discretion, that the Company is in possession of material, undisclosed information about the Company, then that grant of Options to Non-Employee Directors shall be suspended until the second day after public dissemination of such information, and the price, exercisability dates and option period shall then be determined by reference to such later date. If Stock is not traded on the Over-the-Counter Bulletin Board (“OTCBB”) or on any other securities exchange or stock market on any date a grant would otherwise be awarded, then the grant shall be made the next day thereafter on which Stock is so traded. All Option

2

grants pursuant to this Plan shall be evidenced by a written instrument consistent with the provisions hereof.

(d) Notwithstanding any provision contained herein to the contrary, any grant made pursuant to this Section 4 shall be conditioned on the availability of sufficient shares reserved for issuance under the terms of this Plan at the date of grant of such Option and the approval of this Plan by a majority of the Company’s shareholders. In the event that insufficient shares are then available, the number of shares under Options to be granted shall be reduced to the extent shares are then so available, on the basis of the seniority of the Non-Employee Directors then eligible for grants hereunder (with the Non-Employee Directors having less time of service on the Board being first subject to reduction of the number of shares to be granted under their particular Option), or on such other basis as deemed advisable or appropriate under the circumstances as determined by the Board.

5. Option Price.

The price of the Option shall be the fair market value of the Company’s Stock on the Initial Award Date or Award Date, as the case may be (the “Option Price”). Fair market value of the Stock as of any date means (a) the closing price of the Stock on that date on the principal securities exchange on which the Stock is listed; or (b) if the Stock is not listed on a securities exchange, the average of the high and low sale prices of the Stock on that date as reported on the NASDAQ National Market System; or (c) if the Stock is not listed on the NASDAQ National Market System, the average of the high and low bid quotations for the Stock on that date as reported by the OTCBB; or (d) if none of the foregoing is applicable, an amount at the election of the Board equal to (x) the average between the closing bid and ask prices per share of stock on the last preceding date on which those prices were reported or (y) that amount as determined by the Board.

6. Option Period.

Subject to the limitations set forth in this Plan, an Option granted under this Plan shall vest and become exercisable as follows:

(a) Generally. Except as provided in Section 6(b), each Option shall vest and become exercisable in 33.33% installments on the first, second and third anniversary dates of the respective Initial Award Date or Award Date.

(b) 30-Day Options. A 30-Day Option shall vest and become exercisable on the Option’s respective Initial Award Date or Award Date. No 30-Day Option may be exercised later than 30 days after the Initial Award Date or Award Date of such 30-Day Option. Notwithstanding the preceding sentence, a 30-Day Option granted prior to the effective date of this Plan and which meets the requirements of Section 12 must be exercised during the period commencing on the date of the shareholder approval of this Plan and ending at the close of business on the date that is 30 days next following such shareholder approval.

Subject to the limitations set forth in this Plan, an Option may be exercised at any time after it vests and becomes exercisable, provided that at the time of exercise all of the conditions

3

set forth in this Plan have been met. Notwithstanding the foregoing, no Option granted under this Plan may be exercised later than five years after the date of grant thereof.

7. Payment.

Options shall be exercised by the delivery of written notice to the Company setting forth the number of shares of Stock with respect to which the Option is to be exercised, together with cash, wire transfer, certified check, bank draft or postal or express money order payable to the order of the Company (the “Acceptable Funds”) for an amount equal to the aggregate Option Price of such shares of Stock, or at the election of the Non-Employee Director, by exchanging shares of Stock that has been owned by the Non-Employee Director for at least six months, so long as the total fair market value (determined in accordance with Section 5, as of the date of exercise) of the exchanged shares of Stock plus the Acceptable Funds paid, if any, equals the total Option Price of the shares to be acquired upon exercise of that Option, and specifying the address to which the certificates for such shares are to be mailed. Additionally, if permitted by the Board, shares covered by an Option may be purchased upon exercise, in whole or in part, in accordance with the applicable Option agreement, by authorizing a third party to sell the shares (or a sufficient portion thereof) acquired upon exercise of an Option, and assigning the delivery to the Company of a sufficient amount of the sale proceeds to pay for all the shares acquired through such exercise. Whenever an Option is exercised by exchanging shares of Stock theretofore owned by the Non-Employee Director: (1) no shares of Stock received upon exercise of that Option thereafter may be exchanged to pay the Option Price for additional shares of Stock within the following six months; (2) the aggregate fair market value of the shares of Stock tendered must be equal to or less than the aggregate Option Price of the shares being purchased upon exercise of the Option, and any difference must be paid in Acceptable Funds; and (3) the Optionee shall deliver to the Company certificates registered in the name of such Non-Employee Director representing a number of shares of Stock legally and beneficially owned by such Non-Employee Director, free of all liens, claims, and encumbrances of every kind, accompanied by stock powers duly endorsed in blank by the record holder of the share represented by such certificates, with signature guaranteed by a commercial bank or trust company or by a brokerage firm having a membership on a registered national stock exchange. Such notice may be delivered in person to the Secretary of the Company, or may be sent by mail to the Secretary of the Company, in which case delivery shall be deemed made on the date such notice is received. As promptly as practicable after receipt of such written notification and payment, the Company shall deliver to the Non-Employee Director certificates for the number of shares with respect to which such Option has been so exercised, issued in the Non-Employee Director’s name; provided, that such delivery to the Non-Employee Director shall be deemed effected for all purposes when a stock transfer agent of the Company shall have deposited such certificates in the United States mail, addressed to the Non-Employee Director, at the address specified by the Non-Employee Director. The delivery of certificates upon the exercise of Options is subject to the condition that the person exercising such Option provide the Company with such information as the Company may reasonably request to such exercise, sale or other disposition. No shares may be issued until full payment of the aggregate Option Price therefor has been made.

4

8. Cessation of Service.

If, before the date of expiration of the Option, the Non-Employee Director shall cease to be a director of the Company, the Option shall terminate on the earlier of the date of expiration or the date the Non-Employee Director ceases to be a director.

In the event of death while serving as a director, all unvested installments of Options outstanding shall thereupon automatically be accelerated and become fully vested and exercisable in full, and the Option may be exercised for a period of three years after the Non-Employee Director’s death or, if earlier, the date of expiration of the Option, by the Non-Employee Director’s estate or personal representative, or by the person who acquired the right to exercise the Option by bequest or inheritance or by reason of the Non-Employee Director’s death.

9. Administration and Amendment of this Plan.

The Board of Directors of the Company may amend, alter, or discontinue this Plan at any time, but, except as otherwise provided herein, no amendment, alteration, or discontinuation shall be made that would impair the rights of a grantee under an Option theretofore granted, without the grantee’s consent, or which, without the approval of the Company’s shareholders, would:

(i) increase the number of shares that may be issued under this Plan (except by certain adjustments provided for under this Plan);

(ii) change the class of persons eligible to receive Options under this Plan;

(iii) change the requirements of Section 5 hereof regarding the Option Price; or

(iv) amend this Plan in a manner that would require approval of the Company’s shareholders under applicable law, regulation or rule.

Notwithstanding any of the foregoing, adjustments pursuant to Section 14 shall not be subject to the foregoing limitations of this Section 9.

Options may not be granted under this Plan after the date of termination of this Plan, but Options granted prior to that date shall continue to be exercisable according to their terms.

Subject to the above provisions, the Board of Directors of the Company shall have broad authority to amend this Plan to take into account changes in applicable securities and tax laws and accounting rules, as well as other developments.

Except as permitted under Section 14, the Board of Directors may not, without first obtaining shareholder approval, “reprice” outstanding Options as such term is used by the Securities and Exchange Commission (“SEC”) or NASDAQ or otherwise lower the exercise price of an Option.

10. Transferability.

Except as otherwise provided in this Section 10, the Options granted under this Plan are not transferable other than as designated by the grantee by will or by the laws of descent and

5

distribution, and during the grantee’s life, may be exercised only by the grantee. However, the grantee may transfer the Option for no consideration to or for the benefit of the grantee’s Immediate Family (including, without limitation, to a trust for the exclusive benefit of one or more members of the grantee’s Immediate Family or to a partnership or limited liability company in which on one or more members of the grantee’s Immediate Family are the only partners or members, to an IRA for the exclusive benefit of one or more members of the grantee’s Immediate Family, an entity exempt from federal income tax pursuant to Section 501(c)(3) of the Code or any successor provision and/or a split interest trust or pooled income fund described in Section 2522(c)(2) of the Code or any successor provision), subject to such limits as the Board may establish, and the transferee shall remain subject to all the terms and conditions applicable to such Option prior to such transfer, provided, however, that subsequent transfers of such Option shall be prohibited except for transfers by will or the laws of descent and distribution. The foregoing right to transfer the Option shall apply to the right to consent to amendments to the grant agreement and shall also apply to the right to transfer ancillary rights associated with the Option. The provisions of this Plan concerning events of termination of service shall continue to be applied with respect to the original grantee, following which event(s) any such affected Options shall be exercisable by the transferee only to the extent and for the periods specified therein or in the Option agreement. The Board and the Company shall have no obligation to inform any transferee of an Option of any expiration, termination, lapse or acceleration of such Option. The term “Immediate Family” shall mean the grantee’s spouse, ex-spouse, parents, children, stepchildren, adoptive relationships, sisters, brothers and grandchildren (and, for this purpose, shall also include the grantee). The designation by a grantee of a beneficiary will not constitute a transfer of the Option.

In the discretion of the Board of Directors of the Company, any attempt to transfer an Option other than under the terms of this Plan and the applicable Option agreement may terminate the Option.

11. Miscellaneous.

Except as provided in this Plan, no Non-Employee Director shall have any claim or right to be granted an Option under this Plan. Neither this Plan nor any actions hereunder shall be construed as giving any Director any right to be retained in the service of the Company or to continue to be nominated for election as a Director of the Company.

12. Effective Date and Term of Plan.

This Plan shall be effective as of October 26, 2004, the date of its approval by the Board of Directors of the Company, only if shareholder approval of this Plan is obtained at the 2004 Annual Meeting of Shareholders (the “2004 Meeting”). If shareholder approval is not obtained at the 2004 Meeting, no grants of Options shall be effective under this Plan. Any grants made under this Plan prior to shareholder approval of this Plan shall be effective as of the date of such grant but only if the Option agreement related to such grant expressly provides that the Option is conditioned upon or subject to shareholder approval of this Plan. This Plan shall remain in effect through October 26, 2009, or until earlier amended, altered or discontinued in accordance with the terms hereof.

6

13. No Rights As Shareholders.

No Non-Employee Director shall have rights as a shareholder with respect to shares covered by an Option until the date of issuance of a stock certificate for such shares; and, except as otherwise provided in Section 14 hereof, no adjustment for dividends, or otherwise, shall be made if the record date thereof is prior to the date of issuance of such certificate.

14. Changes In The Company’s Capital Structure.

The existence of outstanding Options shall not affect in any way the right or power of the Company or its shareholders to make or authorize any or all adjustments, recapitalizations, reorganizations or other changes in the Company’s capital structure or its business, or any merger or consolidation of the Company, or any issue of bonds, debentures, preferred or prior preference stock ahead of or affecting the Stock or its rights, or the dissolution or liquidation of the Company, or any sale or transfer of all or any part of its assets or business, or any other corporate act or proceeding, whether of a similar character or otherwise.

If the Company shall effect a subdivision or consolidation of shares or other capital readjustment, the payment of a stock dividend, or other increase or reduction of the number of shares of the Stock outstanding, without receiving compensation for it in money, services or property, then (a) the number, class, and per share price of shares of Stock subject to outstanding Options under this Plan shall be appropriately adjusted in such a manner as to entitle a grantee to receive upon exercise of an Option, for the same aggregate cash consideration, the equivalent total number and class of shares he would have received had he exercised his Option in full immediately prior to the event requiring the adjustment; and (b) the number and class of shares of Stock then reserved to be issued under this Plan shall be adjusted by substituting for the total number and class of shares of Stock then reserved, that number and class of shares of Stock that would have been received by the owner of an equal number of outstanding shares of each class of Stock as the result of the event requiring the adjustment.

If the Company is merged or consolidated with another corporation, and the Company is not the surviving corporation, or if the Company is liquidated or sells or otherwise disposes of substantially all of its assets while unexercised Options remain outstanding under this Plan, (a) subject to the provisions of clause (c) below, after the effective date of the merger, consolidations, liquidation, sale or other disposition, as the case may be, each holder of an outstanding Option shall be entitled, upon exercise of the Option, to receive, in lieu of shares of Stock, the number and class or classes of shares of stock or other securities or property to which the holder would have been entitled if, immediately prior to the merger, consolidation, liquidation, sale or other disposition, the holder had been the holder of record of a number of shares of Stock equal to the number of shares as to which the Option shall be so exercised; (b) the Board of Directors may waive any limitations set out in or imposed under this Plan so that all Options, from and after a date prior to the effective date of the merger, consolidation, liquidation, sale or other disposition, as the case may be, specified by the Board of Directors, shall be exercisable in full, to the extent permitted by applicable law; and (c) all outstanding Options may be canceled by the Board of Directors as of the effective date of any merger, consolidation, liquidation, sale or other disposition, if (i) notice of cancellation shall be given to each holder of an Option and (ii) each holder of an Option shall have the right to exercise that Option in full (without regard to any limitations set out in or imposed under this Plan or the written agreement granting that Option) during a period set by the Board of Directors preceding the effective date

7

of the merger, consolidation, liquidation, sale or other disposition and, if in the event all outstanding Options may not be exercised in full under applicable securities laws without registration of the shares of Stock issuable on exercise of the Options, the Board of Directors may limit the exercise of the Options to the number of shares of Stock, if any, as may be issued without registration. The method of choosing which Options may be exercised, and the number of shares of Stock for which Options may be exercised, shall be solely within the discretion of the Board of Directors.

The issue by the Company of shares of stock of any class, or securities convertible into shares of stock of any class, for cash or property, or for labor or services either upon direct sale or upon the exercise of rights or warrants to subscribe for them, or upon conversion of shares or obligations of the Company convertible into shares or other securities, shall not affect, and no adjustment by reason of such issuance shall be made with respect to, the number, class, or price of shares of Stock then subject to outstanding Options.

15. Change in Control of the Company.

In the event of a Change in Control of the Company, then, notwithstanding any other provision in the Plan to the contrary, all unvested installments of Options outstanding shall thereupon automatically be accelerated and exercisable in full. For purposes of this Agreement, a “Change in Control of the Company” shall mean the occurrence of any of the following after the effective date of this Plan:

(a) The acquisition by any individual, entity or group (within the meaning of Section 13(d)(3) or 14(d)(2) of the Exchange Act) (a “Covered Person”) of beneficial ownership (within the meaning of Rule 13d-3 promulgated under the Exchange Act) of 30% or more of either (i) the then outstanding shares of the common stock of the Company (the “Outstanding Company Common Stock”), or (ii) the combined voting power of the then outstanding voting securities of the Company entitled to vote generally in the election of directors (the “Outstanding Company Voting Securities”); provided, however, that for purposes of this subsection (a) of this Section 15, the following acquisitions shall not constitute a Change in Control of the Company: (i) any acquisition directly from the Company, (ii) any acquisition by the Company, (iii) any acquisition by any employee benefit plan (or related trust) sponsored or maintained by the Company or any entity controlled by the Company, or (iv) any acquisition by any corporation pursuant to a transaction which complies with clauses (i), (ii) and (iii) of subsection (c) of this Section 15; or

(b) Individuals who, as of the effective date of this Plan, constitute the Board of Directors (the “Incumbent Board”) cease for any reason to constitute at least a majority of the Board of Directors; provided, however, that any individual becoming a director subsequent to the effective date of this Plan whose election, or nomination for election by the Company’s shareholders, was approved by a vote of at least two-thirds of the directors then comprising the Incumbent Board shall be considered as though such individual were a member of the Incumbent Board, but excluding, for this purpose, any such individual whose initial assumption of office occurs as a result of an actual or threatened election contest with respect to the election or removal of directors or other

8

actual or threatened solicitation of proxies or consents by or on behalf of a Covered Person other than the Board; or

(c) Consummation of (xx) a reorganization, merger or consolidation or sale of the Company or any subsidiary of the Company, or (yy) a disposition of all or substantially all of the assets of the Company (a “Business Combination”), in each case, unless, following such Business Combination, (i) all or substantially all of the individuals and entities who were the beneficial owners, respectively, of the Outstanding Company Common Stock and Outstanding Company Voting Securities immediately prior to such Business Combination beneficially own, direct or indirectly, more than 50% of, respectively, the then outstanding shares of common stock and the combined voting power of the then outstanding voting securities entitled to vote generally in the election of directors, as the case may be, of the corporation resulting from such Business Combination (including, without limitation, a corporation which as a result of such transaction owns the Company or all or substantially all of the Company’s assets either directly or through one or more subsidiaries) in substantially the same proportions as their ownership immediately prior to such Business Combination of the Outstanding Company Common Stock and Outstanding Company Voting Securities, as the case may be, (ii) no Covered Person (excluding any employee benefit plan (or related trust) of the Company or such corporation resulting from such Business Combination) beneficially owns, directly or indirectly, 30% or more of, respectively, the then outstanding shares of common stock of the corporation resulting from such Business Combination or the combined voting power of the then outstanding voting securities of such corporation, except to the extent that such ownership existed prior to the Business Combination, and (iii) at least a majority of the members of the board of directors of the corporation resulting from such Business Combination were members of the Incumbent Board at the time of the execution of the initial agreement, or of the action of the Board of Directors, providing for such Business Combination.

16. Compliance With SEC Regulations.

It is the Company’s intent that this Plan comply in all respects with Rule 16b-3 of the Securities Exchange Act of 1934, as amended (the “Exchange Act”), and any successor rule pursuant thereto. If any provision of this Plan is later found not to be in compliance with the Rule, the provision shall be deemed null and void or shall be reformed by the Board of Directors in such manner so as to comply. All grants of Options and issuance of Stock and all exercises of Options under this Plan shall be executed in accordance with the requirements of Section 16 of the Exchange Act and any regulations promulgated thereunder, so as to avoid the consequences of noncompliance to the Non-Employee Directors.

17. Options In Substitution for Options Granted By Other Corporations.

Options may be granted under this Plan from time to time in substitution for such stock options held by directors of a corporation who become or are about to become directors of the Company as the result of a merger or consolidation of the corporation with the Company or a subsidiary or the acquisition by either of the foregoing of stock of the corporation as the result of which it becomes a subsidiary.

9

18. Investment Intent.

The Company may require that there be presented to and filed with it by any grantee(s) under this Plan, such evidence as it may deem necessary to establish that the Options granted or the shares of Stock to be purchased or transferred are being acquired for investment and not with a view to their distribution.

19. Indemnification of Board.

No current or previous member of the Board of Directors (or committee thereof), nor any officer or employee of the Company acting on behalf of the Board of Directors (or committee thereof), shall be personally liable for any action, determination, or interpretation taken or made in good faith with respect to this Plan, and all such members of the Board of Directors (or committee thereof) and each and any officer or employee of the Company acting on its behalf shall, to the extent permitted by law, be fully indemnified and protected by the Company in respect of any such action, determination or interpretation. The foregoing right of indemnification shall not be exclusive of any other rights of indemnification to which such individuals may be entitled under the Company’s Articles of Incorporation or Bylaws, as a matter of law, or otherwise.

20. Governing Law.

This Plan and all determinations made and actions taken pursuant hereto shall be governed by the laws of the State of Texas, without reference to principles of conflict of laws, and shall be construed accordingly.

10