Exhibit 5.1

Consent of Independent Registered Public Accounting Firm

The Board of Directors

Canadian National Railway Company:

We consent to the use of our report dated January 31, 2020, with respect to the consolidated balance sheets of Canadian National Railway Company as of December 31, 2019 and 2018, and the related consolidated statements of income, comprehensive income, changes in shareholders’ equity and cash flows for each of the years in the two-year period ended December 31, 2019, and the related notes (collectively, the “consolidated financial statements”), incorporated herein by reference. Our report refers to a change to the method of accounting for leases. We also consent to the use of our report dated January 31, 2020 on the effectiveness of internal control over financial reporting as of December 31, 2019, incorporated herein by reference and to the reference to our firm under the heading “Independent Auditors” in the prospectus.

/s/ KPMG LLP*

Montreal, Canada

February 11, 2020

*CPA auditor, CA, public accountancy permit No. A123145