Exhibit 5.1

July 18, 2014

Vulcan Materials Company

1200 Urban Center Drive

Birmingham, Alabama 35242

Ladies and Gentlemen:

In my capacity as Senior Vice President and General Counsel for Vulcan Materials Company, a New Jersey corporation (the “Company”), I have examined the Registration Statement on Form S-3 (the “Registration Statement”) in form as proposed to be filed by the Company with the Securities and Exchange Commission (the “Commission”) pursuant to the provisions of the Securities Act of 1933, as amended, relating to the sale by the selling shareholders of an aggregate of 689,592 shares (the “Shares”) of the common stock, par value $1.00 per share, of the Company (the “Common Stock”), that are issued and outstanding. In this connection, I have examined such records, documents and proceedings as I have deemed relevant and necessary as a basis for the opinions expressed herein. This opinion is provided pursuant to the requirements of Item 16 of Form S-3 and Item 601(b)(5) of Regulation S-K of the Commission.

Upon the basis of the foregoing, I am of the opinion that the Shares have been duly authorized and are validly issued, fully paid and nonassessable.

This opinion is limited to the laws of the State of New Jersey, and I am expressing no opinion as to the effect of the laws of any other jurisdiction. This opinion is rendered as of the date hereof, and I undertake no obligation to advise you of any changes in applicable law or any other matters that may come to my attention after the date hereof.

I hereby consent to the filing of this opinion with the Commission as an exhibit to the Registration Statement. In addition, I hereby consent to the inclusion of the statements made in reference to me under the caption “Legal Matters” in the Registration Statement.

Yours very truly,

  /s/ Michael R. Mills

Michael R. Mills

Senior Vice President and General Counsel