Exhibit 5.1

May 25, 2016

Nokia Corporation

P.O. Box 226

FIN-00045 NOKIA GROUP

FINLAND

Ladies and Gentlemen,

I am Vice President, Corporate Legal of Nokia Corporation, a company incorporated under the laws of the Republic of Finland (the “Company”), and, as such, I have acted on behalf of the Company in connection with its offering of awards (the “Awards”) of performance shares (the “Performance Shares”) pursuant to the Nokia Performance Share Plan 2016 with respect to the shares of the Company, to eligible Company employees in the United States as part of a worldwide employee offering (the “Employee Offering”) that is being undertaken to incentivise selected employees of the Company and its subsidiaries and affiliates. Holders of the Awards will be entitled to receive shares of the Company (each, a “Share”), American Depository Shares (the “ADSs”), each representing one Share, are listed on the New York Stock Exchange.

In connection with the opinions expressed below, I have examined:

(i) the terms and conditions of the Nokia Performance Share Plan 2016, as approved by the Board of Directors of the Company on February 10, 2016 and restated thereby on May 25, 2016;

(ii) the form of documentation to be furnished to employees eligible to participate in the Employee Offering, including a copy of the prospectuses prepared in accordance with the requirements of Part I of Form S-8 under the United States Securities Act of 1933, as amended (the “Securities Act”);

(iii) a signed copy of the Company’s Registration Statement on Form S-8 (the “Registration Statement”) relating to the Employee Offering, which Registration Statement is being filed by the Company with the United States Securities and Exchange Commission (the “Commission”) on the date hereof;

(iv) the Articles of Association of the Company; and

(v) originals, or copies certified or otherwise identified to my satisfaction, of such documents, as I have deemed necessary and appropriate as a basis for the opinion hereinafter expressed.

Based on the foregoing and having regard for such legal considerations as I deem relevant, I am of the opinion that: (1) the Performance Shares to be offered to eligible Company employees pursuant to the Employee Offering will represent legal, valid and binding obligations of the Company enforceable against the Company in accordance with their terms and (2) the Shares to be issued upon settlement of the Performance Shares in connection with the Employee Offering will, upon issuance, be duly authorized, validly issued, fully paid and non-assessable.

I hereby consent to the use of this opinion as Exhibit 5.1 to the Registration Statement. In giving this consent, I do not admit that I am in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission thereunder. I am a lawyer admitted to practice in Finland and I am not admitted in, do not hold myself as being an expert on, and do not express any opinion on the law of any jurisdiction other than the laws of the Republic of Finland.

Very truly yours,

/s/ Riikka Tieaho

Riikka Tieaho

Vice President, Corporate Legal