CONSULTING AGREEMENT

Exhibit 10.1

CONSULTING AGREEMENT

This Consulting Agreement (“Agreement”) is entered into this 26th day of January, 2012, by and between Altria Group, Inc., a Virginia corporation (the “Company”), and Michael E. Szymanczyk (“Szymanczyk”).

RECITALS

Szymanczyk currently is employed as Chief Executive Officer of the Company and Chairman of the Board of Directors of the Company.

Szymanczyk has announced his intention to retire from the Company effective June 1, 2012 (the “Retirement Date”) and not stand for re-election to the Board of Directors of the Company (the “Board”) at the Company’s 2012 Annual Meeting of Shareholders. The Company and Szymanczyk have entered into an Agreement and General Release of even date herewith (the “Separation Agreement”).

The Company, in recognition of Szymanczyk’s ability to provide critical advice to the Board and its new Chief Executive Officer, desires to retain Szymanczyk to render certain consulting services to the Company for 20 months after his retirement from the Company on the terms and conditions set forth in this Agreement, and Szymanczyk desires to be retained by the Company on such terms and conditions.

NOW, THEREFORE, in consideration of the foregoing and mutual covenants set forth below, the Company and Szymanczyk agree as follows:

1. Duties and Engagement. During the Term (defined below), Szymanczyk agrees to render consulting services to the Company on such matters as the Board or Chief Executive Officer may request within Szymanczyk’s knowledge and experience related to the businesses of the Company and its subsidiaries (collectively, the “Services”). The Services shall include, without limitation, assisting the new Chief Executive Officer with his transition, serving as a strategic advisor to the Chief Executive Officer and other senior management, advising on the Company’s strategic planning process, assisting with preparation for Board meetings, and advising and assisting on such other matters as may be requested by the Board or Chief Executive Officer and agreed to by Szymanczyk, which agreement may not be unreasonably withheld. Szymanczyk shall provide Services for at least twenty (20) hours per month and for no more than thirty (30) hours per month. Notwithstanding the foregoing, Szymanczyk’s level of services shall not exceed twenty (20) percent of the average level of services that Szymanczyk performed over the thirty-six month (36) period immediately preceding the Retirement Date, consistent with the parties’ intent that Szymanczyk’s retirement shall constitute a “separation from service” within the meaning of Section 409A of the Internal Revenue Code.

1

2. Effective Date and Term. The term of this Agreement shall commence on the Retirement Date and shall end on January 31, 2014, unless earlier terminated as provided in Section 9 of this Agreement (the “Term”). If the Company wishes to renew this Agreement, it shall inform Szymanczyk in writing at least 30 days prior to the expiration of the Term. By mutual written agreement, this Agreement or any extension thereof may be renewed for additional terms and under such conditions as the parties may agree.

Should Szymanczyk’s employment with the Company terminate for any reason prior to May 31, 2012, (i) this Agreement shall never become effective and (ii) the original terms and conditions of the Restricted Stock Agreements (as defined below) as then in effect shall apply with full force and effect.

3. Compensation and Equity.

a. As compensation for Szymanczyk’s performance of the Services and the obligations stated in Section 7, the Company, having obtained the appropriate approvals from the Compensation Committee of the Board, agrees to make a payment with respect to Szymanczyk’s Deferred Stock Award as described in the Separation Agreement and to amend the 2008 and 2010 Restricted Stock Agreements between the Company and Szymanczyk (the “Restricted Stock Agreements”) to provide as follows and as described in Section 10:

i. Szymanczyk’s April 23, 2008 Restricted Stock award of 200,000 shares of Company stock shall continue to vest during the Term as if Szymanczyk was an employee during such period, in accordance with the terms of the 2008 Restricted Stock Agreement, as amended, notwithstanding Szymanczyk’s termination of employment.

ii. Szymanczyk’s January 26, 2010 Restricted Stock award of 250,000 shares of Company stock shall continue to vest during the Term as if Szymanczyk was an employee during such period, in accordance with the terms of the 2010 Restricted Stock Agreement, as amended, notwithstanding Szymanczyk’s termination of employment.

iii. Such amendments shall become effective as of May 31, 2012.

b. Szymanczyk shall receive no other compensation in connection with his performance of the Services.

4. Travel and Expenses.

a. The Services shall be rendered at the Company’s corporate headquarters in Richmond, Virginia or at such other mutually agreeable location. During the Term, the Company agrees to provide Szymanczyk with office space and secretarial support at the Company’s corporate headquarters in Richmond.

2

b. The Company agrees to provide to Szymanczyk use of Company aircraft for Company business when air travel is required to perform the Services, including travel to and from his residences outside of Virginia. Szymanczyk’s family members may accompany him on such business travel; provided that Szymanczyk shall reimburse the Company for the incremental cost, if any, for their travel. Szymanczyk shall be responsible for any taxes due associated with such travel by him or his family members.

c. The Company shall reimburse Szymanczyk for all reasonable out-of-pocket business expenses incurred by him in connection with the performance of the Services within 30 days following his delivery of such documentation of those expenses in the manner required under the Company’s applicable travel and expense policies.

5. Independent Contractor Status. During the Term and any renewal period, Szymanczyk shall be an independent contractor, and not an employee or agent of the Company or any of its affiliates. Szymanczyk shall not have authority to assume, create or incur any liabilities or obligations of any kind against or on behalf of the Company. Further, Szymanczyk shall not be entitled to any compensation or to participate as an employee in any employee benefit programs of the Company, except those incentive and other payments provided in connection with his separation from the Company and to the extent he is eligible to participate as a retiree of the Company under the Company’s employee benefit plans.

6. Taxes. Szymanczyk acknowledges and agrees that, as an independent contractor, he shall bear sole responsibility for rendering his services, including payments of all taxes and other governmental payments required for anyone to operate a business or consultancy, including without limitation, the payment of all federal, state and local income taxes, self-employment FICA (social security) taxes, and unemployment and workers compensation payments.

7. Confidentiality, Non-Competition and Intellectual Property. As part of the consideration of this Agreement, the parties agree that the Executive Confidentiality and Non-Competition Agreement between Szymanczyk and the Company, dated February 17, 2011 and attached hereto (the “Confidentiality and Non-Competition Agreement”), shall remain in full force and effect except as modified by this Section 7. The parties further agree that:

a. All obligations Szymanczyk had under the Confidentiality and Non-Competition Agreement as an employee of the Company shall continue to apply during the Term and any renewal period, provided that Szymanczyk shall not be required to devote his full-time efforts to the business of the Company;

b. The 18-month post-employment restriction period referenced in Paragraphs 6 and 7 of the Confidentiality and Non-Competition Agreement shall commence upon the expiration or earlier termination of this Agreement, but the three-year and 12-month periods referred to in Paragraph 6 of the Confidentiality and Non-Competition Agreement shall be based on Szymanczyk’s actual date of termination of employment;

3

c. This Section 7 shall be deemed a proper amendment to the Confidentiality and Non-Competition Agreement; and

d. This Section 7 shall survive the termination of this Agreement.

8. Indemnification. The Company and Szymanczyk acknowledge and agree that (i) the Company’s Restated Articles of Incorporation (“Articles”) provide for the exculpation, indemnification and the advancement and reimbursement of legal and other expenses for former officers and directors among other eligible persons; and (ii) in Szymanczyk’s capacity as a consultant under the Consulting Agreement, the Company shall (a) provide for Szymanczyk’s exculpation and indemnification and the advancement and reimbursement of his legal and other expenses to the full extent that the Articles provide such protection to the Company’s officers, and (b) maintain liability insurance coverage for Szymanczyk to the full extent that the Company provides such coverage to its officers.

9. Termination. This Agreement will terminate and be of no further force or effect upon the occurrence of any of the following events:

a. Szymanczyk dies;

b. The Company, by written notice to Szymanczyk, terminates this Agreement due to Szymanczyk’s Disability. As used in this Agreement, “Disability” shall mean a permanent and total disability as determined under procedures established by the Company for the purposes of the Altria Group, Inc. 2005 Performance Incentive Plan;

c. The Company terminates this Agreement for Cause. As used in this Agreement, the term “Cause” shall mean: (i) Szymanczyk’s conviction of (or plea of guilty or nolo contendere to) (A) any felony or (B) any misdemeanor involving fraud or dishonesty in connection with the performance of the Services or moral turpitude; or (ii) the willful failure of Szymanczyk to substantially perform the Services (other than any such failure resulting from illness, injury, or Disability); or (iii) Szymanczyk has willfully engaged in misconduct which has, or can reasonably be expected to have, a material adverse effect on the Company or its businesses; or (iv) Szymanczyk has materially breached his obligations under Section 7 of this Agreement, the Confidentiality and Non-Competition Agreement, or the Separation Agreement. For purposes of this section, the Company, in its reasonable discretion, shall determine whether any action or failure to act by Szymanczyk is deemed willful; provided, however, that no act or failure to act by Szymanczyk shall be deemed considered willful unless he acted in bad faith or without a reasonable belief that his act or omission was in the best interest of the Company;

d. The Company terminates this Agreement for any reason other than for Cause or Disability, which the Company may do at any time;

4

e. Szymanczyk voluntarily terminates his services due to a material default by the Company in the performance of any of its obligations under this Agreement, which default remains unremedied by the Company for a period of 15 days following its receipt of written notice by Szymanczyk (“Good Reason”); or

f. Szymanczyk voluntarily terminates his services for any reason other than Good Reason, which Szymanczyk may do at any time with at least 30 days’ advance notice to the Company.

10. Effects of Termination.

a. If the Agreement is terminated under Section 9(a), 9(b), 9(d) or 9(e) of this Agreement, the Company shall perform all of its obligations under Section 3 of this Agreement and all shares under the Restricted Stock Agreements that remain unvested as of the termination date shall vest in accordance with the Restricted Stock Agreements (as amended).

b. If the Agreement is terminated under Section 9(c) or 9(f) of this Agreement, the Company has no further obligations under Section 3 of this Agreement and Szymanczyk shall forfeit his rights to all shares under the Award Agreements that remain unvested as of the termination date.

11. Severability. If any provision of this Agreement is held by a court of competent jurisdiction to be invalid, void, or unenforceable, the remaining provisions shall nevertheless continue in full force and effect.

12. Notices. All notices and other communications hereunder shall be in writing. Any notice or other communication hereunder shall be deemed duly given if it is sent by registered or certified mail, return receipt requested, postage prepaid to the intended recipient as set forth:

If to Szymanczyk, to his current residence maintained in the Company’s records.

If to the Company, to:

Altria Client Services Inc.

6601 West Broad Street

Richmond, VA 23230

Attn: SVP, Human Resources & Compliance

Any party may send any notice or other communication hereunder to the intended recipient at the address above using any other means (including personal delivery, courier, or electronic mail), but no such notice or other communication shall be deemed to have been duly given unless and until it is actually received by the intended recipient.

5

13. Entire Agreement. This Agreement, the Separation Agreement and the Confidentiality and Non-Competition Agreement set forth the entire agreement between the parties, and except as otherwise provided herein, fully supersede any and all prior agreements, understandings, or representations between the parties pertaining to the subject matter of this Agreement. This Agreement may not be changed, modified or terminated, in whole or in part, except by an instrument in writing signed by the parties hereto.

14. Choice of Law. This Agreement shall be deemed performable by all parties in the Commonwealth of Virginia, and the construction and enforcement of this Agreement shall be governed by Virginia law without regard to its conflict of laws rules.

15. Binding Effect of Agreement. This Agreement shall be binding upon Szymanczyk, the Company and their heirs, administrators, representatives, executors, successors and permitted assigns.

The parties have duly executed this Agreement as of the date first written above.

Senior Vice President, Human Resources & Compliance

Altria Client Services, on behalf of the Company.

6