Exhibit 5.1

Nelson

Mullins

Nelson Mullins Riley & Scarborough LLP

Attorneys and Counselors at Law

50 N. Laura Street, Suite 2800 / Jacksonville, FL 32202

Tel: 904.665.3600 Fax: 904.665.3699

www.nelsonmullins.com

December 6, 2014

Ladies and Gentlemen:

This firm is counsel to FRP Holdings, Inc., a Florida corporation (the “Company”). This letter is being delivered in connection with the Post-Effective Amendment No. 2 (the “Post-Effective Amendment”) to the Registration Statement on Form S-8 (File No. 333-55132) (the “Registration Statement”), under the Securities Act of 1933, as amended (the “Securities Act”), originally filed by Patriot Transportation Holding, Inc., a Florida corporation (the “Predecessor Registrant”), relating to the registration by the Predecessor Registrant of shares of common stock, par value $0.10 per share (the “Predecessor Common Stock”), of the Predecessor Registrant issuable to the Patriot Transportation Holding, Inc. 2000 Stock Option Plan (the “Plan”).

The Company became the successor to the Predecessor Registrant on December 3, 2014 for purposes of Rule 414 under the Securities Act as a result of the merger (the “Merger”) of the Predecessor Registrant with the Company’s wholly owned subsidiary, Patriot Merger Sub Inc., a Florida corporation (the “Merger Sub”), with the Predecessor Registrant being the surviving corporation. Upon effectiveness of the Merger, the separate corporate existence of Merger Sub ceased and the Predecessor Registrant became a direct, wholly owned subsidiary of the Company. In connection with the Merger, the Company assumed and adopted the Plan and as a result, shares of FRP Common Stock (as defined below) are issuable pursuant thereto.

The Registration Statement, as amended by the Post-Effective Amendment, relates to the offering and sale by the Company of certain shares of the Company’s common stock, par value $0.10 per share (“Holdings Common Stock”) issuable pursuant to the Plan.

We have examined the Registration Statement, the Post-Effective Amendment and the Plan. We also have examined the originals or duplicates or certified or conformed copies of such records, agreements, documents and other instruments and have made such other investigations as we have deemed relevant and necessary in connection with the opinions expressed herein. In rendering the opinions below, we have assumed the genuineness of all signatures, the legal capacity of natural persons, the authenticity of all documents submitted to me as originals, the conformity to the original documents of all documents submitted to me as duplicates or certified or conformed copies and the authenticity of the originals of such latter documents.

With offices in the District of Columbia, Florida, Georgia, Massachusetts, North Carolina, South Carolina, Tennessee and West Virginia

Based upon the foregoing, and subject to the qualifications and limitations stated herein, we are of the opinion that the shares of FRP Common Stock and have been duly authorized for issuance under the Plan and, upon their issuance and delivery in accordance with the Plan, will be validly issued, fully paid and non-assessable.

We do not express any opinion herein concerning any law other than the law of the State of Florida and the federal law of the United States.

We hereby consent to the filing of this opinion as Exhibit 5.1 to the Post-Effective Amendment. 

Very truly yours, 

/s/ Nelson Mullins Riley & Scarborough LLP

Nelson Mullins Riley & Scarborough LLP