Exhibit 5.1

1221 PEACHTREE STREET, N.E. • SUITE 400 • ATLANTA, GEORGIA 30361

TELEPHONE: +1.404.521.3939 • JONESDAY.COM

August 2, 2024

VSE Corporation

3361 Enterprise Way

Miramar, Florida 33025

Re: Registration Statement on Form S-3 filed by VSE Corporation

Ladies and Gentlemen:

We have acted as counsel for VSE Corporation, a Delaware corporation (“the Company”), in connection with the authorization of the possible issuance and sale from time to time, on a delayed basis, by the Company of: (i) debt securities of the Company (“Debt Securities”), in one or more series, which may be issued as either senior or subordinated debt or as senior or subordinated convertible debt which may be convertible into or exchangeable for Common Stock (as defined below) or other securities; (ii) shares of common stock, par value $0.05 per share, of the Company (“Common Stock”); (iii) rights to purchase Common Stock, Debt Securities or other securities (the “Rights”); (iv) warrants to purchase Common Stock or Debt Securities (the “Warrants”); and (v) contracts to purchase Common Stock at a future date or dates (the “Stock Purchase Contracts”), which may be issued separately or as part of units consisting of a Stock Purchase Contract and Debt Securities or United States treasury securities, securing the holders’ obligations to purchase Common Stock under the Stock Purchase Contracts (the “Stock Purchase Units”), in each case, as contemplated by the Registration Statement on Form S-3 to which this opinion has been filed as an exhibit (as the same may be amended from time to time, the “Registration Statement”). The Debt Securities, Common Stock, the Rights, the Warrants, the Stock Purchase Contracts and the Stock Purchase Units are collectively referred to herein as the “Securities.” The Securities may be offered and sold from time to time pursuant to Rule 415 under the Securities Act of 1933, as amended (the “Securities Act”).

In connection with the opinions expressed herein, we have examined such documents, records and matters of law as we have deemed relevant or necessary for purposes of such opinions. Based on the foregoing, and subject to the further limitations, qualifications and assumptions set forth herein, we are of the opinion that:

1.The Debt Securities, upon receipt by the Company of such lawful consideration therefor as the Company’s Board of Directors (or an authorized committee or subcommittee thereof) may determine, will constitute valid and binding obligations of the Company.

2.The shares of Common Stock, upon receipt by the Company of such lawful consideration therefor having a value not less than the par value thereof as the Company’s Board of Directors (or an authorized committee or subcommittee thereof) may determine, will be validly issued, fully paid and nonassessable.

AMSTERDAM • ATLANTA • BEIJING • BOSTON • BRISBANE • BRUSSELS • CHICAGO • CLEVELAND • COLUMBUS • DALLAS

DETROIT • DUBAI • DÜSSELDORF • FRANKFURT • HONG KONG • HOUSTON • IRVINE • LONDON • LOS ANGELES • MADRID

MELBOURNE • MEXICO CITY • MIAMI • MILAN • MINNEAPOLIS • MUNICH • NEW YORK • PARIS • PERTH • PITTSBURGH

SAN DIEGO • SAN FRANCISCO • SÃO PAULO • SHANGHAI • SILICON VALLEY • SINGAPORE • SYDNEY • TAIPEI • TOKYO • WASHINGTON

VSE Corporation

August 2, 2024

Page 2

3.The Rights, upon receipt by the Company of such lawful consideration therefor as the Company’s Board of Directors (or an authorized committee or subcommittee thereof) may determine, will constitute valid and binding obligations of the Company.

4.The Warrants, upon receipt by the Company of such lawful consideration therefor as the Company’s Board of Directors (or an authorized committee or subcommittee thereof) may determine, will constitute valid and binding obligations of the Company.

5.The Stock Purchase Contracts, upon receipt by the Company of such lawful consideration therefor as the Company’s Board of Directors (or an authorized committee or subcommittee thereof) may determine, will constitute valid and binding obligations of the Company.

6.The Stock Purchase Units, upon receipt by the Company of such lawful consideration therefor as the Company’s Board of Directors (or an authorized committee or subcommittee thereof) may determine, will constitute valid and binding obligations of the Company.

In rendering the foregoing opinions, we have assumed that: (i) the Registration Statement, and any amendments thereto, will have become effective (and will remain effective at the time of issuance of any Securities thereunder); (ii) a prospectus supplement describing each class or series of Securities offered pursuant to the Registration Statement, to the extent required by applicable law and relevant rules and regulations of the Securities and Exchange Commission (the “Commission”), will be timely filed with the Commission; (iii) the definitive terms of each class and/or series of Securities will have been established in accordance with the authorizing resolutions adopted by the Company’s Board of Directors (or an authorized committee or subcommittee thereof), the Company’s Restated Certificate of Incorporation, as amended (the “Certificate of Incorporation”), and applicable law; (iv) the Company will issue and deliver the Securities in the manner contemplated by the Registration Statement and any Securities issuable upon conversion, exchange or exercise of any other Security will have been authorized and reserved for issuance, in each case within the limits of the then remaining authorized but unreserved and unissued amounts of such Securities; (v) the resolutions authorizing the Company to issue, offer and sell the Securities will have been adopted by the Company’s Board of Directors (or an authorized committee or subcommittee thereof) and will be in full force and effect at all times at which the Securities are offered or sold by the Company; (vi) all Securities will be issued in compliance with applicable federal and state securities laws; and (vii) any Indenture, Purchase Rights Agreement, Warrant Agreement or Purchase Contract Agreement (each as defined below) and each Stock Purchase Unit will be governed by and construed in accordance with the laws of the State of New York and will constitute a valid and binding obligation of each party thereto other than the Company.

With respect to any Securities consisting of any series of Debt Securities, we have further assumed that: (i) such Debt Securities will have been issued pursuant to an indenture that has been executed and delivered by the Company and the applicable trustee in a form approved by us

VSE Corporation

August 2, 2024

Page 3

(the “Indenture”), and the Indenture will have been qualified under the Trust Indenture Act of 1939; (ii) all terms of such Debt Securities not provided for in the applicable Indenture will have been established in accordance with the provisions of the applicable Indenture and reflected in appropriate documentation approved by us and, if applicable, authorized, executed and delivered by the Company and the applicable trustee; and (iii) such Debt Securities will be executed, authenticated, issued and delivered in accordance with the provisions of the applicable Indenture.

With respect to any Securities consisting of Rights, we have further assumed that: (i) the purchase rights agreement, approved by us, relating to the Rights (the “Purchase Rights Agreement”) to be entered into between the Company and an entity selected by the Company to act as the purchase rights agent (the “Purchase Rights Agent”) will have been authorized, executed and delivered by the Company and the Purchase Rights Agent and (ii) the Purchase Rights will be authorized, executed and delivered by the Company and the Purchase Rights Agent in accordance with the provisions of the Purchase Rights Agreement.

With respect to any Securities consisting of Warrants, we have further assumed that: (i) the warrant agreement, approved by us, relating to the Warrants (the “Warrant Agreement”) to be entered into between the Company and an entity selected by the Company to act as the warrant agent (the “Warrant Agent”) will have been authorized, executed and delivered by the Company and the Warrant Agent and (ii) the Warrants will be authorized, executed and delivered by the Company and the Warrant Agent in accordance with the provisions of the Warrant Agreement.

With respect to any Securities consisting of Stock Purchase Contracts, we have further assumed that: (i) the purchase contract agreement, approved by us, relating to the Stock Purchase Contracts (the “Purchase Contract Agreement”) to be entered into between the Company and an entity selected by the Company to act as the purchase contract agent (the “Purchase Contract Agent”) will have been authorized, executed and delivered by the Company and the Purchase Contract Agent and (ii) the Stock Purchase Contracts will be authorized, executed and delivered by the Company and the Purchase Contract Agent in accordance with the provisions of the Purchase Contract Agreement.

With respect to any Securities consisting of Stock Purchase Units, we have further assumed that each component of such Stock Purchase Units will be authorized, validly issued, fully paid and nonassessable (to the extent applicable) and will constitute a valid and binding obligation of the Company or any third party (to the extent applicable) as contemplated by the Registration Statement and the applicable Stock Purchase Unit agreement, if any.

The opinions expressed herein are limited by bankruptcy, insolvency, reorganization, fraudulent transfer and fraudulent conveyance, voidable preference, moratorium or other similar laws and related regulations and judicial doctrines from time to time in effect relating to or affecting creditors’ rights generally, and by general equitable principles and public policy considerations, whether such principles and considerations are considered in a proceeding at law or at equity.

As to facts material to the opinions and assumptions expressed herein, we have relied upon oral or written statements and representations of officers and other representatives of the

VSE Corporation

August 2, 2024

Page 4

Company and others. The opinions expressed herein are limited to the laws of the State of New York and the General Corporation Law of the State of Delaware, in each case as currently in effect, and we express no opinion as to the effect of the laws of any other jurisdiction.

We hereby consent to the filing of this opinion as Exhibit 5.1 to the Registration Statement and to the reference to Jones Day under the caption “Legal Matters” in the prospectus constituting a part of the Registration Statement. In giving such consent, we do not thereby admit that we are included in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission promulgated thereunder.

Very truly yours,

/s/ Jones Day