Exhibit 5.1

ALSTON&BIRD LLP

One Atlantic Center

1201 West Peachtree Street

Atlanta, Georgia 30309-3424

404-881-7000

Fax: 404-881-7777

www.alston.com

March 27, 2013

Graphic Packaging Holding Company

1500 Riveredge Parkway

Suite 100

Atlanta, Georgia 30328

Ladies and Gentlemen:

We have acted as counsel to Graphic Packaging Holding Company, a Delaware corporation (the “Company”), in connection with the preparation and filing with the Securities and Exchange Commission (the “Commission”) pursuant to Rule 424(b) of the Securities Act of 1933, as amended (the “Securities Act”), of a prospectus supplement, dated March 21, 2013 (the “Prospectus Supplement”) to the prospectus, dated August 31, 2011 (together with the Prospectus Supplement, the “Prospectus”), included as part of the above-referenced Registration Statement (the “Registration Statement”) relating to the sale by Clayton, Dubilier & Rice Fund V Limited Partnership (“CDR Fund”), Old Town S.A. (“Old Town”), certain affiliates of TPG Global, LLC (“TPG”), and certain Coors family trusts and the Adolph Coors Foundation (together with the CDR Fund, Old Town, and TPG, the “Selling Stockholders”) of 28,000,000 shares (the “Initial Securities”) of common stock, par value $0.01 per share, of the Company (the “Common Stock”), and, at the option of the Underwriters (as defined below), up to an additional 4,200,000 shares of Common Stock (together with the Initial Securities, the “Securities”). The Securities are being issued and sold to the several underwriters (the “Underwriters”) named in the Underwriting Agreement dated as of March 21, 2013 (the “Underwriting Agreement”) by and among the Selling Stockholders, the Company and the Underwriters.

This opinion is being furnished in accordance with the requirements of Item 16 of Form S-3 and Item 601(b)(5) of Regulation S-K under the Securities Act.

In connection with this opinion, we have examined (i) the Company’s Restated Certificate of Incorporation, (ii) the Company’s Amended and Restated Bylaws, (iii) records of proceedings of the Board of Directors of the Company, or committees thereof, (iv) the Registration Statement; (v) the Prospectus; and (vi) the documents filed by the Company pursuant to the Securities Exchange Act of 1934, as amended, and incorporated by reference to the Prospectus as of the date hereof. We also have made such further legal and factual examinations and investigations as we deemed necessary for purposes of expressing the opinion set forth herein.

Atlanta Ÿ Brussels Ÿ Charlotte Ÿ Dallas Ÿ Los Angeles Ÿ New York Ÿ Research Triangle Ÿ Silicon Valley Ÿ Ventura County Ÿ Washington, D.C.

Graphic Packaging Holding Company

March 27, 2013

Page 2

As to certain factual matters relevant to this opinion letter, we have relied conclusively upon the representations and warranties made in the Underwriting Agreement by the parties thereto and originals or copies, certified or otherwise identified to our satisfaction, of such other records, agreements, documents and instruments, including certificates or comparable documents of officers of the Company and of public officials, as we have deemed appropriate as a basis for the opinion hereinafter set forth.

In rendering our opinion set forth below, we have assumed, without any independent verification, (i) the legal capacity of all natural persons, (ii) the genuineness of all signatures, (iii) the authenticity of all documents submitted to us as originals, and (iv) the conformity to the original documents of all documents submitted to us as conformed, facsimile, photostatic or electronic copies.

Our opinion set forth herein is limited to the General Corporation Law of the State of Delaware, applicable provisions of the Constitution of the State of Delaware and reported judicial decisions interpreting such General Corporation Law and Constitution. We do not express any opinion herein with respect to any other laws.

The only opinion rendered by us consists of those matters set forth in the eighth paragraph hereof, and no opinion may be implied or inferred beyond the opinion expressly stated. Our opinion expressed herein is as of the date hereof, and we undertake no obligation to advise you of any changes in applicable law or any other matters that may come to our attention after the date hereof that may affect our opinion expressed herein.

Based upon the foregoing and subject to all of the other limitations, qualifications and assumptions set forth herein, it is our opinion that the Securities have been validly issued, and are fully paid and non-assessable.

This opinion is delivered for use solely in connection with the sale of the Securities in the transactions contemplated by the Registration Statement, the Prospectus Supplement and the Underwriting Agreement and may not be used, circulated, quoted or otherwise relied upon for any other purpose without our express written consent. No opinion may be implied or inferred beyond the opinion expressly stated above. Our opinion expressed herein is as of the date hereof, and we undertake no obligation to advise you of any changes in applicable law or any other matters that may come to our attention after the date hereof that may affect our opinion expressed herein.

We consent to the filing of this opinion letter as an exhibit to a Current Report on Form 8-K and the incorporation by reference as an exhibit to the Registration Statement and to the use of our name under the heading “Legal Matters” in the Prospectus Supplement constituting a part thereof. In giving such consent, we do not thereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission thereunder.

Graphic Packaging Holding Company

March 27, 2013

Page 3