Exhibit 5.1

May 18, 2026

Star Equity Holdings, Inc.

53 Forest Avenue, Suite 101

Old Greenwich, CT 06870

Ladies and Gentlemen:

We have acted as counsel to Star Equity Holdings, Inc., a Delaware corporation (the “Company”), in connection with the preparation and filing with the Securities and Exchange Commission (the “Commission”) of a Prospectus Supplement, dated May 18, 2026 (the “Prospectus Supplement”), to a prospectus filed as part of a Registration Statement on Form S-3 (File No. 333-294548) (the “Registration Statement”) filed on March 24, 2026 and declared effective as of April 1, 2026. The Prospectus Supplement relates to the offer and sale from time to time of shares of the Company’s 10% Series A Cumulative Perpetual Preferred Stock, par value $0.001 per share (the “Series A Preferred Stock”), up to a maximum aggregate amount of $8,700,000 (the “Shares”), pursuant to an At Market Issuance Sales Agreement, dated May 18, 2026, between the Company and Ladenburg Thalmann & Co. Inc. (the “Sales Agreement”). This opinion is being rendered in connection with the filing of the Prospectus Supplement with the Commission. All capitalized terms used herein and not otherwise defined shall have the respective meanings given to them in the Prospectus Supplement.

We have examined such documents and such matters of fact and law as we deem necessary to render the opinions contained herein. In our examination, we have assumed, but have not independently verified, the genuineness of all signatures, the conformity to original documents of all documents submitted to us as certified, facsimile or other copies, and the authenticity of all such documents. As to questions of fact material to this opinion, we have relied on certificates or comparable documents of public officials and of officers and representatives of the Company.

For purposes of this opinion, we have assumed that:

a.the Registration Statement will remain effective at the time of issuance and sale of the Shares;

b.the Shares will be sold at prices and other terms authorized by the Company’s Board of Directors or another duly authorized committee thereof; and

c.at the time of the issuance and sale of the Shares, a sufficient number of shares of Series A Preferred Stock will remain authorized and available for issuance pursuant to the Company’s Certificate of Designations, Rights and Preferences of 10.0% Series A Cumulative Perpetual Preferred Stock and Amended and Restated Certificate of Incorporation, as it then may be amended.

Based on the foregoing, and subject to the qualifications stated herein, we are of the opinion that the Shares offered pursuant to the Prospectus Supplement will be validly issued, fully paid and non-assessable.

The opinions expressed herein are limited to the General Corporation Law of the State of Delaware and we express no opinion as to the effect on the matters covered by this letter of the laws of any other jurisdiction.

We hereby consent to the filing of this letter as Exhibit 5.1 to a Current Report on Form 8-K that will be filed by the Company and incorporated by reference into the Registration Statement and to the reference to our firm in the Prospectus Supplement under the heading “Legal Matters.” In giving such consent, we do not hereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act of 1933, as amended, or the rules and regulations of the Commission.

Very truly yours,

/s/ Baker & Hostetler LLP

BAKER & HOSTETLER LLP