RED HAT, INC. Red Hat, Inc. 2004 Long-Term Incentive Plan, as amended Restricted Stock Unit Agreement (Non-Executive US Participants) Cover Sheet

Exhibit 10.16

RED HAT, INC.

Red Hat, Inc. 2004 Long-Term Incentive Plan, as amended

Restricted Stock Unit Agreement

(Non-Executive US Participants)

Cover Sheet

This Restricted Stock Unit Agreement (the “Agreement”) evidences the grant by Red Hat, Inc., a Delaware corporation (the “Company”), on the date of grant set forth below (the “Grant Date”) to the person named below (the “Participant”) of a Restricted Stock Unit Award (the “Award”) covering the number of restricted stock units (each, an “RSU”) listed below, each representing the right to receive the value of one share of the Company’s common stock, $.0001 par value per share, with a vesting start date (the “Vesting Start Date”) listed below, such Award to be subject to the terms and conditions specified in the Red Hat, Inc. 2004 Long-Term Incentive Plan, as amended (the “Plan”), and in the attached Exhibit A and Appendix A, thereto.

Participant Name:

Grant Date:

Vesting Start Date:

Number of RSUs:

By accepting this Award, the Participant hereby (i) acknowledges that a copy of the Plan and a copy of the Plan prospectus have been delivered to the Participant and additional copies thereof are available upon request from the Company’s Equity Compensation Department and can also be accessed electronically, (ii) acknowledges receipt of a copy of this Cover Sheet and Exhibit A and Appendix A thereto (collectively, the “Agreement”) and accepts the Award subject to all the terms and conditions of the Plan and the Agreement, (iii) represents that the Participant has read and understands the terms and conditions of the Plan, Plan prospectus and Agreement, and (iv) acknowledges that there may be tax consequences due to the Award and that the Participant should consult a tax advisor to determine his or her actual tax consequences. The Participant must accept this Award electronically pursuant to the online acceptance procedure established by the Company within thirty (30) days; otherwise, the Company may, in its sole discretion, rescind the Award in its entirety.

EXHIBIT A

RED HAT, INC.

Red Hat, Inc. 2004 Long-Term Incentive Plan, as amended

Restricted Stock Unit Agreement

(Non-Executive Participants)

Terms and Conditions

1. Grant of RSUs.

The RSUs, each representing the right to receive the value of one share of common stock, $0.0001 par value, of the Company (“Common Stock”), as provided herein, is granted pursuant to and is subject to and governed by the Plan, and, unless otherwise defined in this Agreement, capitalized terms used herein shall have the same meaning as in the Plan. The shares of Common Stock that are issuable upon the vesting of the RSUs are referred to in this Agreement as “Shares.” The RSUs shall be granted to the Participant without payment of consideration (other than continuing services (as described in Section 2 below)).

2. Vesting.

(a) All of the RSUs shall be unvested on the Grant Date. For purposes of this Agreement, RSUs that have not vested as of any particular time in accordance with this Section 2 are referred to as “Unvested RSUs.”

(b) For so long as the Participant maintains continuous service to the Company or one of its Affiliates as an Employee or Director (a “Business Relationship”) throughout the period beginning on the Grant Date and ending on the vesting date set forth below, the RSUs shall become vested according to the schedule set forth below, subject to Sections 3 and 10 hereof:

[As determined by the Compensation Committee]

3. Cessation of Business Relationship. If the Participant’s Business Relationship ceases for any reason, including death, all Unvested RSUs on the date of such cessation will be forfeited. The Participant’s Business Relationship shall be deemed to have ceased on the last day of active service to the Company or an Affiliate and shall not be extended by any notice of termination period. For purposes hereof, a Business Relationship shall not be considered as having ceased during any bona fide leave of

2

absence if such leave of absence has been approved in writing by the Company; in the event of such leave of absence, vesting of the RSUs shall be suspended (and the vesting dates shall be extended by a period equal to the period of the leave of absence) except for any leave under which the Participant has a legal right to return to employment or such other leave as determined by the Company or unless contrary to applicable local law. The vesting of the RSUs shall not be affected by any change in the type of Business Relationship the Participant has with or among the Company and its Affiliates so long as the Participant continuously maintains a Business Relationship.

4. Payment.

(a) Within 60 days following the vesting date of any RSUs pursuant to Sections 2 or 10 and upon the satisfaction of all other applicable conditions as to the RSUs, but in no event later than the 15th day of the third month of the year following the later of the calendar year or the Company’s taxable year, in each case, in which the RSUs vest, the Company shall distribute to the Participant the Shares represented by RSUs that vested on such vesting date, reduced by the number of Shares (if any) that are withheld from the Award for the payment of Tax-Related Items (as defined in Section 11 hereof); provided, however, that the Shares may be distributed following the date contemplated in this Section 4(a) to the extent permitted under Section 409A of the Code without the payment becoming subject to, and being treated as “nonqualified deferred compensation” within the meaning of, Section 409A of the Code (such as where the Company reasonably anticipates that the payment will violate federal securities laws or other applicable laws). Payment of any vested RSUs shall be made in whole Shares only and any fractional Shares shall be rounded up.

(b) The Company shall not be obligated to issue Shares to the Participant upon the vesting of any RSUs (or otherwise) unless the issuance and delivery of such Shares shall comply with all relevant provisions of law and other legal requirements including, without limitation, any applicable federal, state or foreign securities laws, any applicable Tax-Related Items and the requirements of any stock exchange upon which Shares may be listed.

(c) Anything in the foregoing to the contrary notwithstanding, RSUs granted under this Agreement may be suspended, delayed or otherwise deferred for any of the reasons contemplated in Sections 3 and 4 only to the extent such suspension, delay or deferral is permitted under U.S. Treas. Reg. §§1.409A-2(b)(7), 1.409A-1(b)(4)(ii) or successor provisions, or as otherwise permitted under Section 409A of the Code.

5. Option of Company to Deliver Cash.

Notwithstanding any of the other provisions of this Agreement, at the time any RSU vests, the Company may elect, in the sole discretion of the Committee, to deliver to the Participant in lieu of the Shares represented by RSUs that vested on such vesting date an equivalent amount of cash (determined by reference to the closing price of the Shares on the principal exchange on which the Shares trade on the applicable vesting date or if such date is not a trading date, on the next preceding trading date). Such payments shall be made no later than the deadline set forth in Section 4(a) hereof. If the Company elects to deliver cash to the Participant, the Company is authorized to retain such amount as is sufficient to satisfy the withholding of Tax-Related Items (as defined in Section 11 hereof).

3

6. Restrictions on Transfer.

(a) The Participant shall not sell, assign, transfer, pledge, hypothecate or otherwise encumber or dispose of any RSUs, either voluntarily or by operation of law. Any attempt to dispose of any RSUs in contravention of the above restriction shall be null and void and without effect.

(b) The Company shall not be required (i) to transfer on its books any of the RSUs which have been transferred in violation of any of the provisions set forth herein or (ii) to treat as the owner of such RSUs any transferee to whom such RSUs have been transferred in violation of any of the provisions contained herein.

7. No Obligation to Continue Business Relationship. Neither the Plan, this Agreement, nor the grant of the RSUs imposes any obligation on the Company or its Affiliates to have or continue a Business Relationship with the Participant.

8. No Rights as Stockholder. The RSUs represent an unfunded, unsecured promise by the Company to deliver Shares or the value thereof upon vesting of the RSUs. The Participant shall have no rights as a shareholder with respect to the Shares underlying the RSUs. The Participant shall have no right to vote or receive dividends with respect to any Shares underlying the RSUs or receive dividends unless and until such Shares are distributed to the Participant or converted into Restricted Stock as provided in Appendix A.

9. Adjustments for Capital Changes. The Plan contains provisions covering the treatment of RSUs in a number of contingencies such as stock splits and mergers. Provisions in the Plan for such adjustments are hereby made applicable hereunder and are incorporated herein by reference.

10. Change in Control. Provisions regarding a Change in Control are set forth in Appendix A.

11. Withholding Taxes.

(a) Regardless of any action the Company and/or the Affiliate employing the Participant (the “Employer”) take with respect to any or all income tax (including U.S. federal, state and local tax and/or non-U.S. tax), social insurance, payroll tax or other tax-related items (“Tax-Related Items”), the Participant hereby acknowledges that the ultimate liability for all Tax-Related Items legally due by the Participant with respect to the Participant’s Award of RSUs, vesting of the RSUs, or the issuance of Shares (or payment of cash) in settlement of vested RSUs is and remains the Participant’s responsibility and that the Company and/or the Employer (i) make no representations or undertakings regarding the treatment of any Tax-Related Items in connection with any aspect of the RSUs, including the award of the RSUs, the vesting of the RSUs, the issuance of Shares (or payment of cash) in settlement of the RSUs, the subsequent sale of Shares acquired at vesting and the receipt of any dividends and or Dividend Equivalents; and (ii) do not commit to structure the terms of the Award or any aspect of the RSUs to reduce or eliminate the Participant’s liability for Tax-Related Items.

(b) Prior to the relevant tax withholding event, as applicable, the Participant shall pay or make adequate arrangements satisfactory to the Company and/or the Employer to satisfy all

4

withholding obligations of the Company and/or the Employer with respect to Tax-Related Items. In this regard, the Participant hereby authorizes the Company and/or the Employer, in their sole discretion and without any notice to or authorization by the Participant, to withhold from the Shares being distributed under this Award upon vesting that number of whole Shares the fair market value of which (determined by reference to the closing price of the Common Stock on the principal exchange on which the Common Stock trades on the date the withholding obligation arises, or if such date is not a trading date, on the next preceding trading date) is equal to the aggregate withholding obligation as determined by the Company and/or Employer with respect to such Award, provided that the Company only withholds the number of Shares necessary to satisfy the minimum withholding amount. If the Company satisfies the withholding obligation for Tax-Related Items by withholding a number of Shares being distributed under the Award as described above, the Participant hereby acknowledges that the Participant is deemed to have been issued the full number of Shares subject to the Award of RSUs, notwithstanding that a number of the Shares is held back solely for the purpose of paying the Tax-Related Items due as a result of the Award, vesting and/or settlement of the RSUs. In the event the Tax-Related Items withholding obligation would result in a fractional number of Shares to be withheld by the Company, such number of Shares to be withheld shall be rounded up to the next nearest number of whole Shares. If, due to rounding of Shares, the value of the number of Shares retained by the Company pursuant to this provision is more than the amount required to be withheld, then the Company may pay such excess amount to the relevant tax authority as additional withholding with respect to the Participant.

(c) Alternatively, or in addition, the Company may, (a) only to the extent and in the manner permitted by all applicable securities laws, including making any necessary securities registration or taking any other necessary actions, sell, or instruct the broker whom it has selected for this purpose to sell, the Shares to be issued upon the vesting or settlement, as applicable, of the Participant’s RSUs to meet the withholding obligation for Tax-Related Items, and/or (b) withhold all applicable Tax-Related Items legally payable by Participant from Participant’s wages or other cash compensation paid to Participant by the Company and/or the Employer.

(d) Finally, the Participant hereby acknowledges that the Participant is required to pay to the Employer any amount of Tax-Related Items that the Employer may be required to withhold as a result of the Participant’s Award of RSUs, vesting of the RSUs, or the issuance of Shares (or payment of cash) in settlement of vested RSUs that cannot be satisfied by the means previously described. The Participant hereby acknowledges that the Company may refuse to deliver the Shares in settlement of the vested RSUs to the Participant if the Participant fails to comply with the Participant’s obligations in connection with the Tax-Related Items as described in this Section 11. The Participant shall have no further rights with respect to any Shares that are retained by the Company pursuant to this provision, and under no circumstances will the Company be required to issue any fractional Shares.

(e) The Participant has reviewed and understands the tax obligations as set forth in this Agreement and understands that the Company is not providing any tax advice and that the Participant should consult with Participant’s own tax advisors on the U.S. federal, state, foreign and local tax and non-U.S. tax consequences of this investment and the transactions contemplated by this Agreement.

5

12. Nature of Grant. In accepting the RSUs, Participant acknowledges that: (a) the grant of the RSUs is voluntary and occasional and does not create any contractual or other right to receive future grants of RSUs, or benefits in lieu of RSUs even if RSUs have been granted repeatedly in the past; (b) all decisions with respect to future awards of RSUs, if any, will be at the sole discretion of the Company; (c) the future value of the underlying Shares is unknown and cannot be predicted with certainty; (d) in consideration of the award of RSUs, no claim or entitlement to compensation or damages shall arise from termination of the RSUs or any diminution in value of the RSUs or Shares received when the RSUs vest resulting from the Participant’s termination of employment by the Company or any Affiliate (for any reason whatsoever and whether or not in breach of local employment laws), and Participant irrevocably releases the Company and/or the Affiliate from any such claim that may arise; (e) in the event of involuntary termination of Participant’s employment (whether or not in breach of local employment laws), Participant’s right to receive RSUs and vest under the Plan, if any, will terminate effective as of the date that Participant is no longer actively employed and will not be extended by any notice period mandated under local law or contract, and the Company shall have the exclusive discretion to determine when Participant is no longer actively employed for purposes of the RSUs; (f) the Company is not providing any tax, legal or financial advice, nor is the Company making any recommendations regarding Participant’s participation in the Plan, or Participant’s acquisition or sale of the underlying Shares; and (g) Participant is hereby advised to consult with his or her own personal tax, legal and financial advisors regarding Participant’s participation in the Plan before taking any action related to the Plan.

13. Miscellaneous.

(a) Notices. All notices hereunder shall be in writing and shall be deemed given when sent by certified or registered mail, postage prepaid, return receipt requested, if to the Participant, to the address set forth on the cover sheet or at the most recent address shown on the records of the Company, and if to the Company, to the Company’s principal office, attention of the Corporate Secretary.

(b) Entire Agreement; Modification. This Agreement (including the cover sheet) and the Plan constitutes the entire agreement between the parties relative to the subject matter hereof, and supersedes all other communications between the parties relating to the subject matter of this Agreement. This Agreement may be modified, amended or rescinded by the Committee as it shall deem advisable, subject to any requirement for shareholder approval imposed by applicable law or other applicable rules, including, without limitation, the rules of the stock exchange on which the Shares are listed. If the Committee determines that the Award terms could result in adverse tax consequences to the Participant, the Committee may amend this Agreement without the consent of the Participant in order to minimize or eliminate such tax treatment.

(c) Plan Governs. This Agreement is subject to all terms and provisions of the Plan. In the event of a conflict between one or more provisions of this Agreement and one or more provisions of the Plan, the provisions of the Plan will govern.

(d) Severability. The invalidity, illegality or unenforceability of any provision of this Agreement shall in no way affect the validity, legality or enforceability of any other provision.

6

(e) Successors and Assigns. This Agreement shall inure to the benefit of and be binding upon the heirs, legatees, distributees, executors and administrators of the Participant and the successors and assigns of the Company.

(f) Participant’s Acceptance. The Participant is urged to read this Agreement carefully and to consult with his or her own legal counsel regarding the terms and consequences of this Agreement and the legal and binding effect of this Agreement. By virtue of his or her acceptance of this Agreement, the Participant is deemed to have accepted and agreed to all of the terms and conditions of this Award and the provisions of the Plan, including as binding, conclusive and final all decisions or interpretations of the Committee upon any questions arising under the Plan or this Award.

(g) Section 409A. This Agreement, the RSUs and payments made pursuant to this Agreement are intended to comply with or qualify for an exemption from the requirements of Section 409A of the Code (“Section 409A”) and shall be construed consistently therewith and shall be interpreted in a manner consistent with that intention. Terms defined in the Agreement shall have the meanings given such terms under Section 409A if and to the extent required to comply with Section 409A. Notwithstanding any other provision of this Agreement, the Company reserves the right, to the extent the Company deems necessary or advisable, in its sole discretion, to unilaterally amend the Plan and/or this Agreement to ensure that all RSUs are awarded in a manner that qualifies for exemption from or complies with Section 409A, provided, however, that the Company makes no undertaking to preclude Section 409A from applying to this RSU award. Any payments described in this Section 13(g) that are due within the “short term deferral period” as defined in Section 409A shall not be treated as deferred compensation unless applicable law requires otherwise. If and to the extent any portion of any payment, compensation or other benefit provided to the Participant in connection with his employment termination is determined to constitute “nonqualified deferred compensation” within the meaning of Section 409A and the Participant is a specified employee as defined in Section 409A(2)(B)(i) of the Code, as determined by the Company in accordance with its procedures, by which determination the Participant hereby agrees that he is bound, such portion of the payment, compensation or other benefit shall not be paid before the day that is six months plus one day after the date of separation from service (as determined under Section 409A (the “New Payment Date”)), except as Section 409A may then permit. The aggregate of any payments that otherwise would have been paid to the Participant during the period between the date of separation from service and the New Payment Date shall be paid to the Participant in a lump sum on such New Payment Date, and any remaining payments will be paid on their original schedule. Notwithstanding the foregoing, the Company, its Affiliates, Directors, Officers and Agents shall have no liability to a Participant, or any other party, if the Award that is intended to be exempt from, or compliant with, Section 409A is not so exempt or compliant, or for any action taken by the Committee.

(h) Governing Law/Choice of Venue. This Agreement shall be governed by and interpreted in accordance with the laws of the state of Delaware, without giving effect to the principles of the conflicts of laws thereof. For purposes of litigating any dispute that arises directly or indirectly from the relationship of the parties, evidenced by this Award or the Agreement, the parties hereby submit to and consent to the exclusive jurisdiction of the State of North Carolina and agree that such litigation shall be conducted only in the courts of Wake County, North Carolina, or the federal courts for the United States for the Tenth District of North Carolina, and no other courts, where this Award is made and/or to be performed.

7

(i) Administrator Authority. The Committee will have the power to interpret the Plan and this Agreement and to adopt such rules for the administration, interpretation and application of the Plan as are consistent therewith and to interpret or revoke any such rules (including, but not limited to, the determination of whether or not any RSUs have vested). All actions taken and all interpretations and determinations made by the Committee in good faith will be final and binding upon Participant, the Company and all other interested persons.

8

APPENDIX A

Restricted Stock Unit Agreement

(Non-Executive Participants)

(a) Notwithstanding anything contained herein to the contrary, if (i) this Agreement is continued, assumed, converted or substituted for immediately following a Change in Control and (ii) within one year after a Change in Control the Participant’s Business Relationship is terminated by the Company or its successor without Good Cause (as defined below), all of the RSUs shall be treated as vested and Shares or the value thereof upon vesting shall be delivered in accordance with Sections 4 and 5 hereof. Furthermore and notwithstanding anything contained herein to the contrary, if this Agreement is not continued, assumed, converted or substituted for immediately following the Change in Control, the Participant shall receive a lump sum cash payment within 30 days after the Change in Control in an amount equal to the amount that would have been delivered in accordance with Section 5 hereof had the RSUs fully vested upon the Change in Control.

(b) For purposes of paragraph (a) hereof, this Agreement shall be considered to be continued, assumed, converted or substituted for:

(c) For purposes of this Agreement, the following terms shall have the assigned meanings:

10

Notwithstanding the foregoing, a Change in Control shall not be deemed to occur solely because any person acquires beneficial ownership of more than 35% of the Company Voting Securities as a result of the acquisition of Company Voting Securities by the Company which reduces the number of Company Voting Securities outstanding; provided, that if after such acquisition by the Company such person becomes the beneficial owner of additional Company Voting Securities that increases the percentage of outstanding Company Voting Securities beneficially owned by such person, a Change in Control of the Company shall then occur.

11

12