Exhibit 5.1

October 19, 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 filing of the Company’s Registration Statement on Form S-4 (the “Registration Statement”) with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Securities Act”), relating to the registration of up to 3,836,801 shares of the Company’s 10.0% Series A Cumulative Perpetual Preferred Stock, $0.001 par value per share (the “Preferred Stock”). The securities described in the foregoing clause shall be referred to herein as the “Registered Securities”, and are to be issued pursuant to the terms of the Agreement and Plan of Merger dated as of August 14, 2026 (the “Merger Agreement”), by and among the Company, Merger Sub - R, Inc., a Delaware corporation and wholly owned subsidiary of the Company (“Merger Sub”), and Harte Hanks, Inc., a Delaware corporation (“Harte Hanks”), pursuant to which, among other matters, and subject to the satisfaction or waiver of the conditions set forth in the Merger Agreement, Merger Sub will merge with and into Harte Hanks, with Harte Hanks continuing as the surviving corporation of the merger (the “Merger”), and a wholly owned subsidiary of the Company. Capitalized terms used but not otherwise defined herein shall have the meanings assigned to them in the Merger Agreement.

The Registered Securities consist of shares of Preferred Stock to be issued as merger consideration in respect of shares of common stock, par value $1.00 per share, of Harte Hanks (the “Harte Hanks Common Stock”) and certain Harte Hanks equity awards pursuant to the Merger Agreement. The number of Registered Securities is subject to adjustment in accordance with the Merger Agreement, and the term “Registered Securities” shall include any additional shares of Preferred Stock registered by the Company pursuant to Rule 462(b) under the Securities Act in connection with the offering contemplated by the Registration Statement.

The Merger is subject to satisfaction or waiver of a number of closing conditions, including receipt of the requisite approval of the Harte Hanks stockholders.

This opinion letter is being delivered in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act.

We have examined the Registration Statement, the Merger Agreement, the Company’s Certificate of Designations, Rights and Preferences for the Preferred Stock, the Company’s certificate of incorporation and bylaws and the resolutions adopted by the Company’s board of directors relating to the Registration Statement, the Merger Agreement, and the issuance of the Registered Securities by the Company, and such other instruments, documents, certificates and records that we have deemed relevant and necessary for the basis of our opinions hereinafter expressed.

In such examination, we have assumed: (i) the authenticity of original documents and the genuineness of all signatures; (ii) the conformity to the originals of all documents submitted to us as copies; (iii) the truth, accuracy and completeness of the information, representations and warranties contained in the instruments, documents, certificates and records we have reviewed; (iv) that the Registration Statement, as finally amended, shall have become effective and remain effective under the Securities Act at the time of issuance and sale of the Registered Securities; (v) that the Registered Securities will be issued and sold in compliance with applicable U.S. federal and state securities laws and in the manner stated in the Registration Statement; (vi) that the consummation of the Merger shall have been approved by the stockholders of Harte Hanks; (vii) that the Merger shall have become effective under the General Corporation Law of the State of Delaware (the “DGCL”) and (viii) the legal capacity of all natural persons. As to any facts material to the opinions expressed herein that were not independently established or verified, we have relied upon oral or written statements and representations of officers and other representatives of the Company.

Based on such examination, we are of the opinion that the Registered Securities have been duly authorized and, upon issuance and delivery as merger consideration in respect of shares of Harte Hanks Common Stock and certain Harte Hanks equity awards in accordance with the terms of the Merger Agreement, the Registered Securities will be validly issued, fully paid and non-assessable.

Our opinions are subject to bankruptcy, insolvency, reorganization, moratorium, fraudulent conveyance, fraudulent transfer and other similar laws relating to or affecting creditors’ rights generally and to general equitable principles (regardless of whether considered in a proceeding in equity or at law), including concepts of commercial reasonableness, good faith and fair dealing and the possible unavailability of specific performance or injunctive relief.

We express no opinion as to the laws of any other jurisdiction, other than the federal laws of the United States of America and the DGCL. We do not express any opinion as to the effect on the matters covered by this letter of the laws of any other jurisdiction. The opinion expressed above is as of the date hereof only, and we express no opinion as to, and assume no responsibility for, the effect of any fact or circumstance occurring, or of which we learn, subsequent to the date of this opinion letter, including, without limitation, legislative and other changes in the law or changes in circumstances affecting any party. We assume no responsibility to update this opinion letter for, or to advise you of, any such facts or circumstances of which we become aware, regardless of whether or not they affect the opinion expressed in this opinion letter.

We hereby consent to the filing of this letter as Exhibit 5.1 to the Registration Statement. We further consent to the incorporation by reference of this letter and consent into any registration statement or post-effective amendment to the Registration Statement filed pursuant to Rule 462(b) under the Securities Act with respect to the Registered Securities. 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 or the rules and regulations of the Commission.

Very truly yours,

BAKER & HOSTETLER LLP