Exhibit 5.1

[LETTERHEAD OF LOWENSTEIN SANDLER LLP]

March 30, 2015

Vulcan Materials Company

1200 Urban Center Drive

Birmingham, Alabama 35242

Ladies and Gentlemen:

We have acted as special New Jersey counsel for Vulcan Materials Company, a New Jersey corporation (the “Company”), in connection with the Registration Statement on Form S-3 (Registration No. 333-202769) filed with the Securities and Exchange Commission (the “Registration Statement”), together with the form of prospectus, dated March 16, 2015 (the “Base Prospectus”) included therein, and the proposed sale pursuant to a preliminary prospectus supplement, dated March 16, 2015 (the “Pricing Prospectus”), to the Base Prospectus, and the prospectus supplement, dated March 16, 2015, filed pursuant to Rule 424 promulgated under the Securities Act of 1933, as amended (the “Act”) (together with the Base Prospectus and the Pricing Prospectus, the “Prospectus”), and the Underwriting Agreement, dated March 16, 2015, among the Company and the underwriters named therein (the “Underwriting Agreement”) by the Company of $400,000,000 aggregate principal amount of 4.50% Notes due 2025 (the “Securities”). We have represented the Company in connection with certain transactions on matters relating to New Jersey corporate law, but do not generally represent the Company nor act as the Company’s regular outside counsel.

In connection with rendering the opinions contained in this letter, we have examined originals or copies certified or otherwise identified to our satisfaction of only the following documents:

(a) the Registration Statement;

(b) the Prospectus;

(c) the Senior Debt Indenture, dated as of December 11, 2007 (the “Base Indenture”), together with the Fifth Supplemental Indenture, dated as of March 30, 2015 (together with the Base Indenture, the “Indenture”) between the Company and Regions Bank as successor to Wilmington Trust Company, as Trustee (the “Trustee”), relating to the Securities;

Vulcan Materials Company

March 30, 2015

Page 2

(d) the Underwriting Agreement;

(e) the Officer’s Certificate of the Company dated as of even date herewith (the “Officer’s Certificate”); and

(f) a certificate of standing relating to the Company from the Treasurer of the State of New Jersey, dated March 27, 2015 (the “Good Standing Certificate”).

Upon the basis of such examination and subject to each of the qualifications referred to herein, we advise you that, in our opinion:

1. The Company is a corporation duly incorporated and validly existing in good standing under the laws of the State of New Jersey.

2. The Indenture pursuant to which the Securities are being issued has been duly authorized, executed and delivered by the Company.

3. The Securities have been duly authorized, executed and delivered by the Company.

4. The issue and sale of the Securities and the compliance by the Company with the provisions of the Securities, the Indenture and the Underwriting Agreement and the consummation of the transactions therein contemplated will not result in any violation of (a) the provisions of the Certificate of Incorporation or By-Laws of the Company or (b) any New Jersey law applicable to the Company.

This opinion letter is based upon the customary practice of lawyers who regularly give, and lawyers who regularly advise opinion recipients regarding, opinions of the kind rendered in this opinion letter. For the avoidance of doubt, our opinions do not cover any federal or state securities laws, other antifraud laws and fraudulent transfer laws, tax laws, the Employee Retirement Income Security Act of 1974, antitrust laws or any law that is applicable to the Company, the Underwriting Agreement or the transactions contemplated thereby in the manner set forth therein solely as part of a regulatory regime applicable to the Company or its affiliates due to its or their status, business or assets, nor do our opinions cover the laws of any jurisdiction (including the laws of the State of New Jersey) wherein any holder of the Securities may be located which limit rates of interest that may be charged or collected by such holder.

The opinions expressed herein relate only to laws which are specifically referred to in this letter and to which, in our experience, are normally applicable to transactions of the type

Vulcan Materials Company

March 30, 2015

Page 3

contemplated by the Underwriting Agreement. We have not undertaken any research for purposes of determining whether any parties to any agreement or any of the transactions which may occur in connection with the Underwriting Agreement are subject to any law or other governmental requirement that is not generally applicable to transactions of the type provided for in the Underwriting Agreement.

In rendering the opinions contained herein, we have, with your approval, relied without investigation or independent verification on (i) information obtained from public officials and officers of the Company, (ii) factual information provided to us in the Officer’s Certificate, the Registration Statement, and the Prospectus and (iii) representations in the Underwriting Agreement by the Company and the Underwriters. We have assumed without investigation that the information upon which we have relied is accurate and does not omit disclosures necessary to prevent such information from being misleading. We have also not conducted a search of any electronic databases or the dockets of any court, administrative or regulatory body, agency or other filing office in any jurisdiction or otherwise attempted to independently verify any information or assumptions contained herein.

We have assumed that the Underwriting Agreement, the Indenture and the transactions contemplated thereby were duly authorized, executed and delivered by each party thereto other than the Company, and that the Underwriting Agreement, the Indenture and the transactions contemplated thereby constitute the valid and binding obligation of each party thereto, including the Company, enforceable against each such party, including the Company, in accordance with its terms. Other than as expressly set forth in Paragraph 4 above, we have also assumed that at the time thereof and at all times subsequent thereto, such executions, deliveries, performances and transactions by the Company and by each other party thereto, did not, does not now, and will not violate, result in a breach of, conflict with, or (with or without the giving of notice or the passage of time or both) entitle any party to terminate or call a default under any term of any contract, agreement, instrument, lease, license, arrangement or understanding to which the Company, any Underwriter, or any such other party is or becomes a party or to which any of them or any of their respective properties, assets or security holders are or will be subject, and none of such Underwriters and none of such other parties is subject to any impediment to which contracting parties generally are not subject.

We have further assumed the legal capacity of all natural persons, the genuineness of all signatures, the authenticity of all documents submitted to us as originals, the conformity to original documents of documents submitted to us as certified, facsimile, conformed, electronic or photostatic copies and the authenticity of the originals of such copies. We have assumed that with respect to each offer, issuance, sale and delivery by the Company of Securities pursuant to the Underwriting Agreement and each purchase of such Securities by the Underwriters (a) except for the corporation laws (but not the ‘blue sky’ laws or securities laws as to which we do not

Vulcan Materials Company

March 30, 2015

Page 4

opine) of the State of New Jersey as applicable to the Company, at the time thereof and at all times subsequent thereto, such offer, issuance, sale, delivery, and purchase, the execution, delivery and performance of the Underwriting Agreement and of the other documents relating thereto or delivered in connection therewith, and the consummation of the transactions contemplated by any thereof, as to the Company, any Underwriter or any other party thereto, did not violate, result in a breach of, or conflict with any law, rule, regulation, order, judgment, or decree, in each case whether then or subsequently in effect; (b) at the time thereof and at all times subsequent thereto, the persons authorizing each such offer, issuance, sale, delivery, purchase, execution, performance or transaction for the Company, for any Underwriter or for any such other party did not violate any fiduciary or other duty owed by them; and (c) no event has taken place subsequent to any such offer, issuance, sale, delivery, purchase, execution, performance or transaction or will take place which would cause any such offer, issuance, sale, delivery, purchase, execution, performance or transaction not to comply with any such law, rule, regulation, order, judgment, decree or duty, or which would permit the Company, any Underwriter, or any such other party at any time thereafter to cancel, rescind, or otherwise avoid any such offer, issuance, sale, delivery, purchase, execution, performance, transaction or document. In rendering the foregoing opinions, we have assumed without investigation that no party to the Underwriting Agreement at any time from the execution thereof until immediately after the closing contemplated thereby has been in violation of, or in default in complying with any provision thereof and that all conditions to the consummation of the transactions contemplated thereby shall have been satisfied at or prior to such closing.

In rendering the opinion set forth in Paragraph 1 above as to the good standing of the Company, we have relied exclusively on the Good Standing Certificate and our opinion in that Paragraph is given solely as of the date and time of such certificate.

We have assumed the solvency of the Company. In addition, we are expressing no opinion in Paragraph 4 above, insofar as performance by the Company of its obligations under the Underwriting Agreement is concerned, as to bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium and similar laws of general applicability relating to or affecting creditors’ rights.

In rendering the opinions set forth in Paragraphs 2 and 3 above as to the execution of the Indenture and the Securities by the Company, we have relied solely on the Officer’s Certificate. In rendering the opinions set forth in Paragraphs 2 and 3 above as to the delivery by the Company of the Indenture and the Securities, we have assumed with your permission that (a) the laws governing such delivery are substantially similar to the laws of the State of New Jersey and (b) electronic transmission of the Indenture and the Securities has been authorized by the parties to the Indenture and the Securities for purposes of delivery.

Vulcan Materials Company

March 30, 2015

Page 5

Our advice on each legal issue addressed in this letter represents our opinion as to how that issue would be resolved were it to be considered by the highest court of the jurisdiction upon whose law our opinion on that issue is based. The manner in which any particular issue would be treated in any actual court case would depend in part on facts and circumstances particular to the case, and this letter is not intended to guarantee the outcome of any legal dispute.

The opinions contained herein are limited to the laws of the State of New Jersey as of the date of this letter and we are expressing no opinion as to the effect of the laws of any other jurisdiction.

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