Exhibit 5.1

January 29, 2015

Inovalon Holdings, Inc.

4321 Collington Road

Bowie, Maryland 20716

Re: Registration Statement on Form S-1

Ladies and Gentlemen:

We are acting as counsel to Inovalon Holdings, Inc., a Delaware corporation (the “Company”), in connection with its registration statement on Form S-1 (File No. 333-201321), as amended (the “Registration Statement”), filed with the Securities and Exchange Commission under the Securities Act of 1933, as amended (the “Securities Act”), relating to the proposed public offering of up to 25,555,555 shares (the “Shares”) of the Company’s Class A Common Stock, par value $0.000005 per share (the “Common Stock”), including shares of Common Stock that may be sold pursuant to the underwriters’ option to purchase additional shares, all of which Shares are to be sold by the Company pursuant to the proposed form of Underwriting Agreement among the Company and the underwriters named therein filed as Exhibit 1.1 to the Registration Statement (the “Underwriting Agreement”).

As counsel for the Company, we have examined originals or copies, certified or otherwise identified to our satisfaction, of such documents, corporate records, certificates of public officials and other instruments as we have deemed necessary for the purposes of rendering this opinion and we are familiar with the proceedings taken and proposed to be taken by the Company in connection with the authorization, issuance and sale of the Shares. In our examination, we have assumed the genuineness of all signatures, the authenticity of all documents submitted to us as originals and the conformity with the originals of all documents submitted to us as copies. This opinion letter is given, and all statements herein are made, in the context of the foregoing.

This opinion letter is based as to matters of law solely on the General Corporation Law of the State of Delaware as currently in effect. We express no opinion herein as to any other laws, statutes, ordinances, rules, or regulations.

Based upon the foregoing, we are of the opinion that following (i) execution and delivery by the Company of the Underwriting Agreement, (ii) effectiveness of the Registration Statement, (iii) issuance of the Shares pursuant to the Underwriting Agreement, and (iv) receipt by the

Inovalon Holdings, Inc.
January 29, 2015
Page Two

Company of the consideration for the Shares specified in the resolutions of the Board of Directors of the Company, the Shares will be validly issued, fully paid and nonassessable.

This opinion letter has been prepared for use in connection with the Registration Statement. We assume no obligation to advise you of any changes in the foregoing subsequent to the effective date of the Registration Statement.

We consent to the use of this opinion as an exhibit to the Registration Statement, and we consent to the reference of our name under the caption “Legal Matters” in the Prospectus forming a part of the Registration Statement. In giving such consent, we do not thereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act.