Exhibit 5.1

Ladies and Gentlemen:

We have acted as counsel to you in connection with your filing of a Registration Statement on Form S-1 (File No. 333-257525) (as amended or supplemented, the “Registration Statement”) pursuant to the Securities Act of 1933, as amended (the “Securities Act”), relating to the offer by Outbrain Inc. a Delaware corporation (the “Company”), of up to 9,200,000 shares of its common stock, $0.001 par value (“Common Stock”), including the shares of Common Stock purchasable by the underwriters upon the exercise of their overallotment option (the “Shares”). The Shares are being sold to the several underwriters named in, and pursuant to, an underwriting agreement between the Company and such underwriters (the “Underwriting Agreement”).

In connection with this opinion, we have examined copies, certified or otherwise identified to our satisfaction, of: (i) the Eleventh Amended and Restated Certificate of Incorporation of the Company, dated July 13, 2021, (ii) the Bylaws of the Company as currently in effect; (iii) certain resolutions of the board of directors of the Company, relating to the issuance and sale of the Shares; (iv) the Registration Statement; and (v) the Prospectus. In addition, we have examined originals or copies, certified or otherwise identified to our satisfaction, of certain other corporate records, documents, instruments and certificates of public officials and of the Company, and we have made such inquiries of officers of the Company and public officials and considered such questions of law as we have deemed necessary for purposes of rendering the opinion set forth herein.

In connection with this opinion, we have assumed the genuineness of all signatures and the authenticity of all items submitted to us as originals and the conformity with originals of all items submitted to us as copies. In making our examination of documents executed by parties other than the Company, we have assumed that each other party has the power and authority to execute and deliver, and to perform and observe the provisions of, such documents and has duly authorized, executed and delivered such documents, and that such documents constitute the legal, valid and binding obligations of each such party. We also have assumed the integrity and completeness of the minute books of the Company presented to us for examination.

Based upon, subject to and limited by the foregoing, we are of the opinion that the Shares have been duly and validly authorized and, upon issuance and delivery against payment therefor in accordance with the terms of the Underwriting Agreement, the Shares will be validly issued, fully paid and nonassessable.

Mayer Brown is a global services provider comprising an association of legal practices that are separate entities including
Mayer Brown LLP (Illinois, USA), Mayer Brown International LLP (England), Mayer Brown (a Hong Kong partnership)
and Tauil & Chequer Advogados (a Brazilian partnership).

Mayer Brown LLP

July 19, 2021

Page 2

We do not express any opinion herein concerning any law other than the Delaware General Corporation Law and the federal laws of the United States of America, as in effect on the date hereof.

We hereby consent to the filing of this opinion letter as Exhibit 5.1 to as an exhibit to the Registration Statement, and to the reference to us under the caption “Legal Matters” in the Prospectus, which is a part of the Registration Statement. In giving such consent, we do not hereby admit that we are acting within the category of persons whose consent is required under Section 7 of the Act or the rules or regulations of the Commission thereunder.