EXHIBIT 5.1 Baker & McKenzie LLP Two Embarcadero Center, Suite 1100 San Francisco, California 94111 United States Tel: +1 415 576 3000 Fax: +1 415 576 3099 www.bakermckenzie.com Asia Pacific Bangkok Beijing Brisbane March 6, 2020 Hanoi Ho Chi Minh City Hong Kong Jakarta Kuala Lumpur* Manila* Avaya Holdings Corp. Melbourne Seoul 4655 Great America Parkway Shanghai Singapore Santa Clara, California 95054 Sydney Taipei Tokyo Yangon RE: Registration Statement on Form S-8 for Avaya Holdings Corp. 2020 Employee Stock Europe, Middle East Purchase Plan & Africa Abu Dhabi Almaty Dear Ladies and Gentlemen: Amsterdam Antwerp Bahrain Baku We have acted as special counsel for Avaya Holdings Corp., a Delaware corporation Barcelona Berlin (the “Company”), in connection with its filing with the Securities and Exchange Commission Brussels Budapest (the “SEC”) of a registration statement on Form S-8 filed on the date hereof (the “Registration Cairo Casablanca Statement”) under the Securities Act of 1933, as amended (the “Securities Act”), with respect Doha Dubai to the registration of 5,500,000 shares of the Company’s common stock, par value $0.01 per Dusseldorf Frankfurt/Main share (the “Shares”), issuable pursuant to the Company’s 2020 Employee Stock Purchase Plan Geneva Istanbul (the “Plan”). Jeddah* Johannesburg Kyiv London As the Company’s counsel, we have examined the proceedings taken and are familiar Luxembourg Madrid with the proceedings proposed to be taken by the Company in connection with the sale and Milan Moscow issuance of the Shares under the Plan. We have examined the originals, or photostatic or Munich Paris certified copies, of such records of the Company, of certificates of officers of the Company and Prague Riyadh* of public documents, and such other documents as we have deemed relevant and necessary as Rome St. Petersburg the basis of the opinions set forth below. In such examination, we have assumed the Stockholm Vienna genuineness of all signatures, the authenticity of all documents submitted to us as originals, the Warsaw Zurich conformity to original documents of all documents submitted to us as photostatic or certified The Americas copies, the authenticity of the originals of such copies and that the offer and sale of the Shares Bogota Brasilia** complies in all respects with the terms, conditions and restrictions set forth in the Registration Buenos Aires Caracas Statement and the Plan. We have also assumed that at the time of each issuance of the Shares, Chicago Dallas there will be a sufficient number of shares of the Company’s common stock authorized for Guadalajara Houston issuance under the Company’s certificate of incorporation, as amended, that have not otherwise Juarez Lima been issued or reserved or committed for issuance. Mexico City Miami Monterrey New York Based upon and subject to the limitations, qualifications, exceptions and assumptions Palo Alto Porto Alegre** set forth herein, we are of the opinion that the Shares have been duly and validly authorized, Rio de Janeiro** San Francisco and when issued, sold and delivered in accordance with the terms of the Plan, will be validly Santiago Sao Paulo** issued, fully paid and non-assessable. Tijuana Toronto Valencia Washington, DC The opinions expressed above are limited to the General Corporation Law of the State * Associated Firm of Delaware. ** In cooperation with Trench, Rossi e Watanabe Advogados Baker & McKenzie LLP is a member of Baker & McKenzie International, a Swiss Verein.

This opinion letter is limited to the matters stated herein, and no opinion is implied or may be inferred beyond the matters expressly stated. We consent to the use of this opinion as an exhibit to the Registration Statement, and further consent to the use of our name wherever appearing in the Registration Statement and any amendments thereto. In providing this consent, we do not thereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the SEC promulgated thereunder. Sincerely, /s/ BAKER & McKENZIE LLP BAKER & McKENZIE LLP 2