Exhibit 5.1

[LETTERHEAD OF SKADDEN, ARPS, SLATE, MEAGHER & FLOM LLP]

April 5, 2017

AdvancePierre Foods Holdings, Inc.

9987 Carver Road

Blue Ash, Ohio 45242

Re: AdvancePierre Foods Holdings, Inc.

Registration Statement on Form S-1

Ladies and Gentlemen:

We have acted as special counsel to AdvancePierre Foods Holdings, Inc., a Delaware corporation (the “Company”), in connection with the resale by certain selling stockholders (the “Selling Stockholders”) of an aggregate of 14,375,000 shares of common stock, par value $0.01 per share (“Common Stock”), of the Company (including up to 1,875,000 shares of Common Stock subject to an over-allotment option) (the “Shares”).

This opinion is being furnished in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act of 1933, as amended (the “Securities Act”).

In rendering the opinion stated herein, we have examined and relied upon the following:

(a) the registration statement on Form S-1 of the Company relating to the Shares filed on April 5, 2017 with the Securities and Exchange Commission (the “Commission”) under the Securities Act (such registration statement being hereinafter referred to as the “Registration Statement”);

(b) an executed copy of a certificate of Linn Harson, Senior Vice President, General Counsel and Corporate Secretary of the Company, dated the date hereof (the “Secretary’s Certificate”);

(c) a copy of the Company’s Certificate of Incorporation, as amended and in effect as of the respective dates the Shares were issued;

AdvancePierre Foods Holdings, Inc.

April 5, 2017

Page 2

(d) a copy of the Company’s by-laws, as amended and in effect as of the respective dates the Shares were issued; and

(e) copies of certain resolutions of the Board of Directors of the Company relating to the issuance of the Shares and related matters.

We have also examined originals or copies, certified or otherwise identified to our satisfaction, of such records of the Company and the Selling Stockholders and such agreements, certificates and receipts of public officials, certificates of officers or other representatives of the Company and the Selling Stockholders and others, and such other documents as we have deemed necessary or appropriate as a basis for the opinion stated below, including the facts and conclusions set forth in the Secretary’s Certificate.

In our examination, we have assumed the genuineness of all signatures, including endorsements, the legal capacity and competency of all natural persons, the authenticity of all documents submitted to us as originals, the conformity to original documents of all documents submitted to us as facsimile, electronic, certified or photostatic copies, and the authenticity of the originals of such copies. As to any facts relevant to the opinion stated herein that we did not independently establish or verify, we have relied upon statements and representations of officers and other representatives of the Company and the Selling Stockholders and others and of public officials.

We do not express any opinion with respect to the laws of any jurisdiction other than the General Corporation Law of the State of Delaware (the “DGCL”).

Based upon the foregoing and subject to the qualifications and assumptions stated herein, we are of the opinion that the Shares have been duly authorized by all requisite corporate action on the part of the Company under the DGCL and have been validly issued and are fully paid and nonassessable.

In rendering the foregoing opinion we have assumed that the consideration recited in the resolutions of the Board of Directors of the Company approving the issuance of all of the Shares has been received in full by the Company.

AdvancePierre Foods Holdings, Inc.

April 5, 2017

Page 3

We hereby consent to the reference to our firm under the heading “Legal Matters” in the prospectus forming part of the Registration Statement. We also hereby consent to the filing of this opinion with the Commission as an exhibit to the Registration Statement. 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 Securities Act or the rules and regulations of the Commission.

Very truly yours,

/s/ Skadden, Arps, Slate, Meagher & Flom LLP