EXECUTIVE EMPLOYMENT AGREEMENT

Exhibit 10.16

EXECUTIVE EMPLOYMENT AGREEMENT

This Executive Employment Agreement (this “Agreement”) is made as of December 23, 2008 (the “Effective Date”), by and between BMC Software, Inc., a Delaware corporation (the “Employer”), and Denise M. Clolery (the “Executive”). The Employer and the Executive are each a “party” and are together “parties” to this Agreement.

BACKGROUND

The Employer and the Executive previously entered into that certain employment agreement dated November 28, 2005 (the “Prior Employment Agreement”). The Employer and the Executive now desire to amend and restate the Prior Employment Agreement to reflect necessary changes for the Agreement to comply with Code Section 409A and to make certain other changes.

AGREEMENT

In consideration of the employment compensation to be paid to the Executive and other good and valuable consideration, the receipt and sufficiency of which is hereby acknowledged, the parties, intending to be legally bound, agree as follows:

For the purposes of this Agreement, the following terms have the meanings specified or referred to in this Section 1.

“Affiliate” means a person or entity that directly or indirectly controls, is controlled by, or is under common control with, the Employer.

“Agreement” refers to this Executive Employment Agreement, including all Exhibits attached hereto, as amended from time to time.

“Base Salary” as defined in Section 3.1.

“Benefits” as defined in Section 3.2.

“Board of Directors” refers to the board of directors of the Employer.

“Cause” as defined in Section 6.3(a).

“Change of Control” means the occurrence of one or more of the following events:

(a) the acquisition, directly or indirectly, by any person or related group of persons (within the meaning of Section 13(d)(3) or 14(d)(2) of the Securities Exchange Act of 1934, as amended (the “Exchange Act”) of beneficial ownership (within the

meaning of Rule 13d-3 of the Exchange Act) of securities possessing at least fifty percent (50%) of the total combined voting power of the Employer’s outstanding securities;

(b) a change in the composition of the Board of Directors such that a majority of the Board members ceases by reason of one or more contested elections for Board membership to be comprised of individuals who either (i) are Board members as of the Effective Date (the “Incumbent Directors”) or (ii) after the Effective Date, are elected or nominated for election as Board members by at least a majority of the Incumbent Directors who are still in office at the time such election or nomination is approved by the Board (such individuals will also be considered “Incumbent Directors” upon election to the Board), but excluding for purposes of clauses (i) and (ii) any such individual whose initial assumption of office occurs as a result of an actual or threatened election contest (within the meaning of Rule 14a-11 of the Exchange Act) with respect to the election or removal of directors or other actual or threatened solicitation of proxies or consents by or on behalf of a Person other than the Board of Directors;

(c) a merger, consolidation, or similar corporate transaction in which the Employer’s shareholders immediately prior to the transaction do not own more than sixty percent (60%) of the voting stock of the surviving corporation in the transaction;

(d) shareholder approval of the Employer’s liquidation, dissolution, or sale of substantially all of its assets; or

(e) if Executive’s primary employment duties are with a subsidiary, division or business unit of the Employer, the sale, merger, contribution, transfer or any other transaction in conjunction with which the Employer’s ownership interest in the subsidiary, division or business unit decreases below a majority interest.

“Confidential Information” means any and all:

(a) trade secrets (as defined herein) concerning the business and affairs of the Employer, product specifications, data, know-how, formulae, compositions, processes, designs, sketches, photographs, graphs, drawings, samples, inventions and ideas, past, current, and planned research and development, current and planned manufacturing or distribution methods and processes, customer lists, current and anticipated customer requirements, price lists, market studies, business plans, computer software and programs (including object code and source code), computer software and database technologies, systems, structures, and architectures (and related formulae, compositions, processes, improvements, devices, know-how, inventions, discoveries, concepts, ideas, designs, methods and information), and any other information, however documented, that is a trade secret;

(b) information concerning the business and affairs of the Employer (which includes historical financial statements, financial projections and budgets, historical and projected sales, capital spending budgets and plans, the names and backgrounds of key personnel, personnel training and techniques and materials), however documented; and

2

(c) notes, analysis, compilations, studies, summaries, and other material prepared by or for the Employer containing or based, in whole or in part, on any information included in the foregoing.

“Disability” as defined in Section 6.2.

“Effective Date” is the date stated in the first paragraph of the Agreement.

“Employee Invention” shall mean any idea, invention, technique, modification, process, or improvement (whether patentable or not), any industrial design (whether registerable or not), any mask work, however fixed or encoded, that is suitable to be fixed, embedded or programmed in a semiconductor product (whether recordable or not), and any work of authorship (whether or not copyright protection may be obtained for it) created, conceived, or developed by the Executive, either solely or in conjunction with others, during the Employment Period, or a period that includes a portion of the Employment Period, that relates in any way to, or is useful in any manner in, the business then being conducted or proposed to be conducted by the Employer, and any such item created by the Executive, either solely or in conjunction with others, following termination of the Executive’s employment with the Employer, that is based upon or uses Confidential Information.

“Employer Group” shall mean the Employer and any other corporation or trade or business required to be aggregated with the Employer which constitutes a single employer under Code Section 414(b) or Code Section 414(c) with the Employer, except that in applying Code Section 1563(a)(1), (2), and (3), the language “at least 50 percent” is used instead of “at least 80 percent”.

“Employment Period” is the term of the Executive’s employment under this Agreement.

“Fiscal Year” shall mean the Employer’s fiscal year, which shall end on March 31 of each year, or as changed from time to time.

“Good Reason” as defined in Section 6.3(b).

“Person” is any individual, corporation (including any non-profit corporation), general or limited partnership, limited liability company, joint venture, estate, trust, association, organization, or governmental body.

“Proprietary Items” as defined in Section 7.2(a)(iv).

“Separation from Service ” shall mean the Executive’s termination of employment with the Employer Group for any reason which constitutes a “separation from service” under Code Section 409A. Notwithstanding the foregoing, the Executive’s employment relationship with the Employer Group is considered to remain intact while the individual is on military leave, sick leave or other bona fide leave of absence if there is a reasonable expectation that the Executive will return to perform services for the Employer Group and the period of such leave does not exceed six months, or if longer, so long as the Executive retains a right to reemployment with the Employer under applicable law or contract. Solely for purposes of determining whether a Separation from Service has occurred, the Employer will determine whether the Executive has

3

terminated employment with the Employer Group based on whether it is reasonably anticipated by the Employer and the Executive that the Executive will permanently cease providing services to the Employer Group, whether as an employee or independent contractor, or that the services to be performed by the Executive, whether as an employee or independent contractor, will permanently decrease to no more than 20% of the average level of bona fide services performed, whether as an employee or independent contractor, over the immediately preceding 36-month period or such shorter period during which the Executive was performing services for the Employer Group. If a leave of absence occurs during such 36-month or shorter period which is not considered a Separation from Service, unpaid leaves of absence shall be disregarded and the level of services provided during any paid leave of absence shall be presumed to be the level of services required to receive the compensation paid with respect to such leave of absence.

“Trade Secrets” shall mean the whole or any part of any scientific or technical information, design, process, procedure, formula, or improvement that has value and that the owner has taken measures to prevent from becoming available to persons other than those selected by the owner to have access for limited purposes.

The Employer hereby employs the Executive, and the Executive hereby accepts employment by the Employer, upon the terms and conditions set forth in this Agreement.

Subject to the provisions of Section 6, the term of the Executive’s employment under this Agreement will commence upon the Effective Date and shall continue in effect through the third anniversary of the Effective Date (the “Employment Period”); provided, however, that, subject to the provisions of Section 6, commencing on the day following the Effective Date and on each day thereafter, the Employment Period shall be automatically extended for one additional day unless the Employer shall give written notice to Executive that the Employment Period shall cease to be so extended, in which event the Employment Period shall terminate on the third anniversary of the date such notice is given.

The Executive will have such duties as are assigned or delegated to the Executive by the Board of Directors, and will initially serve as the Employer’s Senior Vice President, General Counsel and Secretary reporting to the Company’s Chief Executive Officer. The Executive will devote her entire business time, attention, skill, and energy exclusively to the business of the Employer, will use her best efforts to promote the success of the Employer’s business, and will cooperate fully with the Board of Directors in the advancement of the best interests of the Employer. The Executive’s employment will be subject to the policies maintained and established by the Employer, from time to time. Nothing in this Section 2.3, however, will prevent the Executive from engaging in additional activities in connection with passive personal investments and community affairs that are not inconsistent with the Executive’s duties under this Agreement. Additionally, nothing in this Section 2.3 will prevent the Executive from serving

4

on the board of directors of other companies or organizations, or engaging in other activities, so long as such participation does not conflict with the interests or business of Employer or require such involvement as to interfere with the performance of the Executive’s duties hereunder and has been expressly approved by the Chief Executive Officer of Employer. If the Executive is elected as a director of the Employer or as a director or officer of any of its affiliates, the Executive will fulfill her duties as such director or officer without additional compensation. The Executive acknowledges and agrees that she owes a fiduciary duty of loyalty, fidelity and allegiance to act at all times in the best interests of the Employer.

During the Employment Period, the Employer shall pay Executive an annual base salary in the amount of $400,000, less applicable taxes and withholdings, payable in accordance with the Employer’s standard payroll practices and procedure (the “Base Salary”). Executive’s Base Salary shall be reviewed at least annually and, if deemed appropriate in the sole discretion of the Compensation Committee of the Board of Directors, shall be increased from time to time.

The Executive will, during the Employment Period, be permitted to participate in such pension, profit sharing, life insurance, hospitalization, major medical, and other employee benefit plans of the Employer that may be in effect from time to time, to the extent the Executive is eligible under the terms of those plans (collectively, the “Benefits”).

Executive will be eligible for a cash bonus as described in Attachment A incorporated herein by reference.

The Executive will be entitled to receive awards granted by the Compensation Committee of the Board of Directors pursuant to any equity program or long-term incentive plan that may be maintained by the Employer from time to time. Executive’s rights respecting any awards granted to the Executive prior to the Effective Date pursuant to any such equity program or long-term incentive plan maintained by the Employer shall continue under the terms of the awards and the applicable plans or programs under which the awards were granted.

The Employer will furnish the Executive office space, equipment, supplies, and such other facilities and personnel as the Employer deems necessary or appropriate for the performance of the Executive’s duties under this Agreement.

5

The Employer will pay on behalf of the Executive (or reimburse the Executive for) reasonable expenses incurred by the Executive at the request of, or on behalf of, the Employer in the performance of the Executive’s duties pursuant to this Agreement, and in accordance with the Employer’s employment policies, including reasonable expenses incurred by the Executive in attending business meetings, in appropriate business entertainment activities, and for promotional expenses. The Executive must file expense reports with respect to such expenses in accordance with the Employer’s policies then in effect.

All in-kind benefits provided and expenses eligible for reimbursement under this Section 4 must be provided by the Employer or incurred by the Executive during the term of this Agreement. All reimbursements shall be paid as soon as administratively practicable, but in no event shall any reimbursement be paid after the last day of the taxable year following the taxable year in which the expense was incurred. The amount of in-kind benefits provided or reimbursable expenses incurred in one taxable year shall not affect the in-kind benefits to be provided or the expenses eligible for reimbursement in any other taxable year. Such right to reimbursement or in-kind benefits is not subject to liquidation or exchange for another benefit.

The Executive will be entitled to paid vacation during the Employment Period in accordance with the vacation policies of the Employer in effect for its employees from time to time. The Executive will also be entitled to the paid holidays and other paid leave set forth in the Employer’s policies.

The Employment Period, the Executive’s Base Salary and any and all other rights of the Executive under this Agreement or otherwise as an employee of the Employer will terminate (except as otherwise provided in this Section 6):

(a) upon the death of the Executive;

(b) upon the Disability (as defined in Section 6.2) of the Executive immediately upon notice from either party to the other;

(c) upon termination by the Employer for Cause (as defined in Section 6.3);

(d) upon the voluntary retirement from or voluntary resignation of employment by the Executive for any reason other than those set forth in Section 6.1(f) below;

6

(e) upon termination by the Employer for any reason other than those set forth in Section 6.1(a) through 6.1(d) above; or

(f) upon voluntary resignation of employment by the Executive for Good Reason, as defined in Section 6.3 below.

Upon termination of the Employment Period, as provided above or otherwise, Executive’s rights respecting benefits, stock options, equity incentives, and cash bonus will be determined under the applicable plan or program providing the same.

For purposes hereof, the term “Disability” shall mean an incapacity by accident, illness or other circumstance which renders the Executive mentally or physically incapable of performing the duties and services required of the Executive hereunder on a full-time basis for a period of at least 180 consecutive days.

(a) Definition of “Cause” . For all purposes under this Agreement, “Cause” shall mean the occurrence of one or more of the following events:

(i) the Executive’s continued and material failure to perform her obligations under this Agreement;

(ii) the Executive’s material failure to adhere to any Employer policy or code of conduct;

(iii) the appropriation (or attempted appropriation) of a material business opportunity of the Employer, including attempting to secure or securing any personal profit in connection with any transaction entered into on behalf of the Employer;

(iv) the Executive’s engaging in conduct that is materially injurious to the Employer;

(v) the misappropriation (or attempted misappropriation) of any of the Employer’s funds or property;

(vi) the conviction of or the entering of a guilty plea or plea of no contest with respect to, a felony, the equivalent thereof, or any other crime with respect to which imprisonment is a punishment; or

(vii) the conviction of the Executive by a court of competent jurisdiction of a crime involving moral turpitude.

7

The determination of whether the Executive’s employment is terminated for Cause shall be made solely by the Employer, which shall act in good faith in making such determination.

(b) Definition of “Good Reason” . For all purposes under this Agreement, “Good Reason” means the occurrence of one or more of the following events arising without the express written consent of the Executive, but only if the Executive notifies the Employer in writing of the event within sixty (60) days following the occurrence of the event, the event remains uncured after the expiration of thirty (30) days from receipt of such notice, and the Executive resigns effective no later than thirty (30) days following the Employer’s failure to cure the event:

(i) the occurrence, prior to a Change of Control or on or after the date which is twelve (12) months after a Change of Control occurs, of any one or more of the following events that results in a material negative change in the Executive’s employment relationship with the Employer:

(A) the Executive no longer being, at a minimum, Senior Vice President – General Counsel and Secretary with substantially similar responsibilities (including an alteration in Executive’s reporting responsibilities);

(B) a reduction in the Executive’s Base Salary or target bonus opportunity from that provided to her immediately on the Effective Date of this Agreement or as the same may be increased from time to time;

(C) a diminution in employee benefits (including but not limited to medical, dental, life insurance and long-term disability plans) and perquisites applicable to the Executive from those substantially similar to the employee benefits and perquisites provided by the Employer (including subsidiaries) to executives with comparable duties, as such benefits may be modified from time to time; or

(D) the Employer or a subsidiary thereof requiring the Executive to be permanently based anywhere other than within fifty (50) miles of Houston, Texas; or

(ii) the occurrence, within twelve (12) months after the date upon which a Change of Control occurs, of any one or more of the following events:

(A) a material diminution in the Executive’s Base Salary;

(B) a material diminution in the Executive’s authority, duties, or responsibilities;

(C) a material diminution in the authority, duties, or responsibilities of the supervisor to whom the Executive is required to

8

report, including a requirement that the Executive report to a corporate officer or employee instead of reporting directly to the board of directors of the Employer;

(D) a material diminution in the budget over which the Executive retains authority;

(E) the Employer or a subsidiary thereof requiring the Executive to be permanently based anywhere other than within fifty (50) miles of the Executive’s job location immediately prior to the reassignment;

(F) any other action that constitutes a material bre