Exhibit 5.1

[LETTERHEAD OF LOWENSTEIN SANDLER LLP]

March 16, 2015

Vulcan Materials Company

1200 Urban Center Drive

Birmingham, Alabama 35242

Re: Vulcan Materials Company Registration Statement on Form S-3

Ladies and Gentlemen:

We have acted as special counsel to Vulcan Materials Company, a New Jersey corporation (the “Company”), in connection with the Registration Statement on Form S-3 (the “Registration Statement”) to be filed on the date hereof by the Company with the Securities and Exchange Commission (the “SEC”) in connection with the registration pursuant to the Securities Act of 1933, as amended (the “Act”), that we understand will be automatically effective under the Act pursuant to Rule 462(e) promulgated thereunder, of an indeterminate amount of the Company’s debt securities (the “Debt Securities”), which may be issued in one or more series under one or more indentures (the “Indentures”), including the Form of Indenture attached as Exhibit 4.1 to the Registration Statement, between the Company and Regions Bank, as successor to Wilmington Trust Company, as trustee (the “Trustee”), shares of the Company’s common stock, $1.00 par value (the “Common Stock”), shares of the Company’s preferred stock, no par value (the “Preference Stock”), depository shares (the “Depository Shares”), warrants (the “Warrants”), stock purchase contracts (the “Stock Purchase Contracts”), stock purchase units (the “Stock Purchase Units”) and such indeterminate amount of Debt Securities, and number of shares of Common Stock or Preference Stock as may be issued upon conversion, exchange or exercise of any Debt Securities, Preference Stock, Depository Shares, Warrants, Stock Purchase Contracts or Stock Purchase Units, including such shares of Common Stock or Preference Stock as may be issued pursuant to anti-dilution adjustments, in amounts, at prices and on terms to be determined at the time of offering. The Debt Securities, Common Stock, the Preference Stock, the Depository Shares, the Warrants, the Stock Purchase Contracts and the Stock Purchase Units are collectively referred to herein as the “Securities”.

In connection with the opinions contained in this letter, we have examined and are familiar with copies of the Registration Statement, the Company’s Restated Certificate of Incorporation, the Company’s By-Laws and the Form of Indenture attached as Exhibit 4.1 to the Registration Statement. In addition, we have examined and relied on originals or copies certified or otherwise identified to our satisfaction of such documents, corporate records, certificates of public officials and other instruments as we have deemed necessary or appropriate for the purposes of the opinions contained herein. In such examination, we have assumed (a) the authenticity of original documents and the genuineness of all signatures; (b) the conformity to the originals of all documents submitted to us as copies; (c) each natural person signing any document reviewed by us had the legal capacity to do so, (d) each person signing in a representative capacity (other than on behalf of the Company) any document reviewed by us had authority to sign in such capacity, (e) the truth, accuracy and completeness of the information,

Page 2 March 16, 2015

representations and warranties contained in the records, documents, instruments and certificates we have reviewed; (f) the Registration Statement, and any amendments thereto (including post-effective amendments), will have become effective under the Act and comply with all applicable laws; (g) a prospectus supplement will have been filed with the SEC describing the Securities offered thereby; (h) any Debt Securities that may be issued will be issued in a form that complies with the Indentures and any Debt Securities, the Indentures and any supplemental indentures to be entered into in connection with the issuance of such Debt Securities will be manually signed or countersigned, as the case may be, by duly authorized officers of the Trustee or authenticating agent; (i) the Indenture and any supplemental indentures to be entered into in connection with the issuance of such Debt Securities will be qualified pursuant to the Trust Indenture Act; (j) all Securities will be issued and sold in compliance with applicable federal and state securities laws, including applicable provisions of “blue sky” laws, and in the manner stated in the Registration Statement and the applicable prospectus supplement; (k) a definitive purchase, underwriting or similar agreement with respect to any Securities offered will have been duly authorized and validly executed and delivered by the Company and the other parties thereto; (l) the organizational documents of the Company, each as amended to the date hereof, will not have been amended from the date hereof in a manner that would affect the validity of any of the opinions rendered herein; (m) any Securities issuable upon conversion, exchange, redemption or exercise of any Securities being offered will be duly authorized, created and, if appropriate, reserved for issuance upon such conversion, exchange, redemption or exercise; (n) with respect to shares of Common Stock or Preference Stock offered, there will be sufficient shares of Common Stock or Preference Stock authorized under the Company’s organizational documents and not otherwise reserved for issuance; (o) with respect to the Debt Securities and the related Indenture, Depository Shares, the Warrants, the Stock Purchase Contracts and the Stock Purchase Units, that each such security and the Indenture, as applicable, is governed by the laws of the State of New Jersey; and (p) with respect to the depository share agreement governing the Depository Shares to be offered by the Company pursuant to the Registration Statement (the “Depository Share Agreement”), that such agreement is governed by the laws of the State of New Jersey. We have also assumed the due authorization and valid execution and delivery by each of the Company and the other parties thereto to each of the Registration Statement, the Indentures, the Debt Securities and any definitive purchase or other similar agreement with respect to any Debt Securities offered (collectively, the “Transaction Documents”), and that the execution, delivery and performance of the Transaction Documents will not (i) violate, conflict with or result in a breach of, or require any consent under, the charters, bylaws or equivalent organizational documents of any such party or the laws of the jurisdictions of organization or applicable laws with respect to such parties, (ii) violate any requirement or restriction imposed by any order, writ, judgment, injunction, decree, determination or award of any court or governmental body having jurisdiction over it or any of its assets or (iii) constitute a breach or violation of any agreement or instrument that is binding upon such parties, and we have assumed that each such other party (in the case of parties which are not natural persons) has been duly organized and is validly existing and in good standing under its jurisdiction of organization, that each such other party has the legal capacity, power and authority (corporate or otherwise) to enter into, deliver and perform its obligations thereunder and that each of the Transaction Documents constitutes the valid and legally binding obligation of all such other parties, enforceable against them in accordance with its terms.

Page 3 March 16, 2015

Our opinions contained herein are expressed solely with respect to the federal laws of the United States and the laws of the State of New Jersey. We express no opinion as to matters involving the laws of any jurisdiction other than the State of New Jersey and the United States. The opinions contained herein are limited to the present corporate laws of the State of New Jersey and the present federal laws of the United States and to the present judicial interpretations thereof and to the facts as they presently exist. We undertake no obligation to advise you as a result of developments occurring after the date hereof or as a result of facts or circumstances brought to our attention after the date hereof.

Based upon the foregoing, and subject to the qualifications set forth in this letter, we are of the opinion that:

1. With respect to any shares of Common Stock to be offered by the Company pursuant to the Registration Statement (the “Offered Common Shares”), when (i) the Registration Statement, as finally amended (including all necessary post-effective amendments), has become effective under the Act, (ii) an appropriate prospectus supplement or term sheet with respect to the Offered Common Shares has been prepared, delivered and filed in compliance with the Act and the applicable rules and regulations thereunder, (iii) if the Offered Common Shares are to be sold pursuant to a firm commitment underwritten offering, the underwriting agreement with respect to the Offered Common Shares has been duly authorized, executed and delivered by the Company and the other parties thereto, (iv) the Board of Directors (the “Board”), including any appropriate committee appointed thereby, and appropriate officers of the Company have taken all necessary corporate action to approve the issuance of the Offered Common Shares, the consideration to be received therefor (which shall be at least equal to the aggregate par value of such shares of Common Stock) and related matters, (v) the terms of the issuance and sale of the Offered Common Shares have been duly established in conformity with the organizational documents of the Company, do not violate any applicable law or result in a default under or breach of any agreement or instrument binding upon the Company and comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company and (vi) certificates in the form required under the New Jersey Business Corporation Act representing the Offered Common Shares are duly executed, countersigned, registered and delivered upon receipt of the agreed-upon consideration therefor, the Offered Common Shares (to the extent such shares of Common Stock are to be issued upon the conversion, exchange or exercise of any Debt Securities, Preference Stock, Depository Shares, Warrants, Stock Purchase Contracts or Stock Purchase Units, registered on the Registration Statement, when such shares have been duly issued and delivered as contemplated by the terms of the applicable Indenture relating to such Debt Securities, the Preference Stock, the Depository Share Agreement relating to such Depository Shares, the Warrant Agreement relating to such Warrants, or the Stock Purchase Contracts or Stock Purchase Units, respectively), when issued and sold in accordance with the applicable underwriting agreement with respect to the Offered Common Shares or any other duly authorized, executed and delivered valid and binding purchase or agency agreement for consideration that shall be at least equal to the aggregate par value of such shares of Common Stock, will be legally issued, fully paid and nonassessable.

2. With respect to the shares of any series of Preference Stock to be offered by the Company pursuant to the Registration Statement (the “Offered Preference Shares”), when (i) the Registration Statement, as finally amended (including all necessary post-effective

Page 4 March 16, 2015

amendments), has become effective under the Act, (ii) an appropriate prospectus supplement or term sheet with respect to the Offered Preference Shares has been prepared, delivered and filed in compliance with the Act and the applicable rules and regulations thereunder, (iii) if the Offered Preference Shares are to be sold pursuant to a firm commitment underwritten offering, the underwriting agreement with respect to the Offered Preference Shares has been duly authorized, executed and delivered by the Company and the other parties thereto, (iv) the Board, including any appropriate committee appointed thereby, and appropriate officers of the Company have taken all necessary corporate action to approve the issuance, terms and sale of the Offered Preference Shares, the consideration to be received therefor and related matters, (v) an amendment to the certificate of incorporation of the Company containing the terms of each new series of Preference Stock has been filed with the New Jersey State Treasurer, (vi) the terms of the Offered Preference Shares and of their issuance and sale have been duly established in conformity with the terms of the particular series as established by the Board, so as not to violate any applicable law, the organizational documents of the Company or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, and (vii) certificates in the form required under the New Jersey Business Corporation Act representing the Offered Preference Shares are duly executed, countersigned, registered and delivered upon receipt of the agreed-upon consideration therefor, the Offered Preference Shares (to the extent such shares of Preference Stock are to be issued upon the conversion, exchange or exercise of any Debt Securities, Preference Stock, Depository Shares, Warrants, Stock Purchase Contracts or Stock Purchase Units, registered on the Registration Statement, when such shares have been duly issued and delivered as contemplated by the terms of the applicable Indenture relating to such Debt Securities, the Preference Stock, the Depository Share Agreement relating to such Depository Shares, the Warrant Agreement relating to such Warrants, or the Stock Purchase Contracts or Stock Purchase Units, respectively), when issued or sold in accordance with the applicable underwriting agreement or any other duly authorized, executed and delivered valid and binding purchase or agency agreement, will be legally issued, fully paid and nonassessable.

3. With respect to any Depository Shares to be offered by the Company pursuant to the Registration Statement (the “Offered Depository Shares”), when (i) the Registration Statement, as finally amended (including all necessary post-effective amendments), has become effective under the Act, (ii) an appropriate prospectus supplement or term sheet with respect to the Offered Depository Shares has been prepared, delivered and filed in compliance with the Act and the applicable rules and regulations thereunder, (iii) the Board, including any appropriate committee appointed thereby, and appropriate officers of the Company have taken all necessary corporate action to approve the issuance of the Offered Depository Shares, the consideration to be received therefor and related matters, (iv) the Depository Share Agreement has been duly authorized, executed and delivered by the Company and the other parties thereto, (v) the terms of the issuance and sale of the Offered Depository Shares have been duly established in conformity with the Depository Share Agreement, so as not to violate any applicable law, the organizational documents of the Company or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, and (vi) the Offered Depository Shares have been duly executed and delivered against receipt of the agreed-upon consideration therefore, pursuant to the Depository Share Agreement, the Company’s obligations under the Depository Share Agreement will be valid, binding and enforceable obligations of the Company.

Page 5 March 16, 2015

4. With respect to any Warrants to be offered by the Company pursuant to the Registration Statement (the “Offered Warrants”), when (i) the Registration Statement, as finally amended (including all necessary post-effective amendments), has become effective under the Act, (ii) an appropriate prospectus supplement or term sheet with respect to the Offered Warrants has been prepared, delivered and filed in compliance with the Act and the applicable rules and regulations thereunder, (iii) the Board, including any appropriate committee appointed thereby, and appropriate officers of the Company have taken all necessary corporate action to approve the issuance of the Offered Warrants, the consideration to be received therefor and related matters, (iv) the warrant agreement with respect to the Offered Warrants (the “Warrant Agreement”) has been duly authorized, executed and delivered by the Company and the other parties thereto, (v) the terms of the issuance and sale of the Offered Warrants have been duly established in conformity with the Warrant Agreement, so as not to violate any applicable law, the organizational documents of the Company or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, and (vi) the Offered Warrants have been duly executed and delivered against receipt of the agreed-upon consideration therefore, pursuant to the Warrant Agreement, the Offered Warrants will be valid, binding and enforceable obligations of the Company.

5. With respect to any Stock Purchase Contracts or Stock Purchase Units to be offered by the Company pursuant to the Registration Statement (the “Offered Stock Purchase Contracts and Stock Purchase Units”), when (i) the Registration Statement, as finally amended (including all necessary post-effective amendments), has become effective under the Act, (ii) an appropriate prospectus supplement or term sheet with respect to the Offered Stock Purchase Contracts and Stock Purchase Units has been prepared, delivered and filed in compliance with the Act and the applicable rules and regulations thereunder, (iii) the Board, including any appropriate committee appointed thereby, and appropriate officers of the Company have taken all necessary corporate action to approve the issuance of the Offered Stock Purchase Contracts and Stock Purchase Units, the consideration to be received therefor and related matters, (iv) the terms of the Offered Stock Purchase Contracts and Stock Purchase Units and of their issuance and sale have been duly established in conformity with the terms as established by the Board, so as not to violate any applicable law, the organizational documents of the Company or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, and (v) the Offered Stock Purchase Contracts and Stock Purchase Units have been duly executed and delivered against receipt of the agreed-upon consideration therefore, pursuant to the relevant Stock Purchase Contract, the Offered Stock Purchase Contracts and Stock Purchase Units will be valid, binding and enforceable obligations of the Company.

6 With respect to any Debt Securities to be offered by the Company pursuant to the Registration Statement (the “Offered Debt Securities”), when (i) the Registration Statement, as finally amended (including all necessary post-effective amendments), has become effective under the Act, (ii) an appropriate prospectus supplement or term sheet with respect to

Page 6 March 16, 2015

the Offered Debt Securities has been prepared, delivered and filed in compliance with the Act and the applicable rules and regulations thereunder, (iii) the Board, including any appropriate committee appointed thereby, and appropriate officers of the Company have taken all necessary corporate action to approve the issuance of the Offered Debt Securities, the consideration to be received therefor and related matters, (iv) if the Offered Debt Securities are to be sold pursuant to a firm commitment underwritten offering, the underwriting agreement with respect to the Offered Debt Securities has been duly authorized, executed and delivered by the Company and the other parties thereto, (v) the terms of the Offered Debt Securities and of their issuance and sale have been duly established in conformity with the terms as established by the Board, so as not to violate any applicable law, the organizational documents of the Company or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company, (vi) the Offered Debt Securities and the applicable Indenture relating to the Offered Debt Securities have been duly executed and countersigned and in the case of the Indenture, duly authenticated by the Trustee, and the Offered Debt Securities have been issued and sold as contemplated by the Registration Statement and any prospectus supplement, and (vii) the Company has received the applicable consideration for the Offered Debt Securities as contemplated by the Registration Statement and any prospectus supplement, the Debt Securities will constitute valid and binding obligations of the Company enforceable against the Company in accordance with their terms.

The foregoing opinions are subject to the effects of (a) bankruptcy, insolvency, fraudulent conveyance, reorganization, moratorium and other similar laws relating to or affecting the enforcement of creditors’ rights generally, (b) general equitable principles (whether considered in a proceeding in equity or at law), (c) an implied covenant of good faith and fair dealing, (d) provisions of law that require that a judgment for money damages rendered by a court in the United States be expressed only in United States dollars, (e) limitations by any governmental authority that limit, delay or prohibit the making of payments outside the United States, (f) usury laws, statutes and regulations, and (g) generally applicable laws that (i) provide for the enforcement of oral waivers or modifications where a material change of position in reliance thereon has occurred or provide that a course of performance may operate as a waiver, (ii) limit the availability of a remedy under certain circumstances where another remedy has been elected, (iii) limit the enforceability of provisions releasing, exculpating or exempting a party from, or requiring indemnification of a party for, liability for its own action or inaction, to the extent the action or inaction involves gross negligence, recklessness, willful misconduct or unlawful conduct, (iv) may, where less than all of a contract may be unenforceable, limit the enforceability of the balance of the contract to circumstances in which the unenforceable portion is not an essential part of the agreed exchange, and (v) may limit the enforceability of provisions providing for compounded interest, imposing increased interest rates or late payment charges upon delinquency in payment or default or providing for liquidated damages or for premiums upon acceleration. We express no opinion as to whether, or the extent to which, the laws of any particular jurisdiction apply to the subject matter hereof, including, without limitation, the enforceability of the governing law provision contained in any Securities and their governing documents.

We express no opinion as to whether, or the extent to which, the laws of any particular jurisdiction apply to the subject matter hereof, including, without limitation, the enforceability of the governing law provision contained in any Securities and their governing documents.

Page 7 March 16, 2015

We hereby consent to the filing of copies of this letter as an exhibit to the Registration Statement and to references to us in the prospectus forming a part of the Registration Statement under the caption “Legal Matters.” In giving this consent, we do not thereby admit that we are within the category of persons whose consent is required under Section 7 of the Act and the rules and regulations thereunder. This letter speaks as of its date, and we undertake no (and hereby disclaim any) obligation to update this letter.

Very truly yours,

/s/ LOWENSTEIN SANDLER LLP