Exhibit 5.1

[Shearman & Sterling LLP letterhead]

December 3, 2012

The Board of Directors

The Dun & Bradstreet Corporation

103 JFK Parkway

Short Hills, New Jersey 07078

The Dun & Bradstreet Corporation

Offering of $450,000,000 3.250% Senior Notes due 2017 &

$300,000,000 4.375% Senior Notes due 2022

Ladies and Gentlemen:

We have acted as counsel to The Dun & Bradstreet Corporation, a Delaware corporation (the “Company”), in connection with the issuance and sale by the Company of $450,000,000 aggregate principal amount of its 3.250% Senior Notes due 2017 (the “2017 Notes”) and $300,000,000 aggregate principal amount of its 4.375% Senior Notes due 2022 (the “2022 Notes” and, together with the 2017 Notes, the “Notes”), pursuant to the Underwriting Agreement, dated November 28, 2012 (the “Underwriting Agreement”), among the Company and the Underwriters named in Schedule II therein. The Notes are to be issued pursuant to the indenture dated as of March 14, 2006 (the “Base Indenture”), between the Company and The Bank of New York Mellon (formerly known as The Bank of New York), as trustee (the “Trustee”), as amended and supplemented by a first supplemental indenture dated as of the date hereof between the Company and the Trustee (the “First Supplemental Indenture”). The Base Indenture, as amended and supplemented by the First Supplemental Indenture, is referred to herein as the “Indenture”.

In that connection, we have reviewed originals or copies of the following documents:

(a) The Underwriting Agreement.

(b) The Indenture.

(c) The form of the Notes.

The documents described in the foregoing clauses (a) through (c) are collectively referred to herein as the “Opinion Documents.”

We have also reviewed the originals or copies of such other corporate records of the Company and its subsidiaries, certificates of public officials and of officers of the Company and its subsidiaries and agreements and other documents as we have deemed necessary as a basis for the opinion expressed below.

In our review of the Opinion Documents and other documents, we have assumed:

(a) The genuineness of all signatures.

(b) The authenticity of the originals of the documents submitted to us.

(c) The conformity to authentic originals of any documents submitted to us as copies.

(d) As to matters of fact, the truthfulness of the representations made in the Opinion Documents and in certificates of public officials and officers of the Company.

(e) That each of the Opinion Documents is the legal, valid and binding obligation of each party thereto, other than the Company, enforceable against each such party in accordance with its terms.

(f) That:

(i) The Company is duly organized and validly existing under the laws of the jurisdiction of its organization.

(ii) The Company has the full power to execute, deliver and perform, and has duly executed and delivered, the Opinion Documents to which it is a party.

(iii) The execution, delivery and performance by the Company of the Opinion Documents do not:

(A) except with respect to Generally Applicable Law, violate any law, rule or regulation applicable to it; or

(B) result in any conflict with or breach of any agreement or document binding on it.

(iv) No authorization, approval, consent or other action by, and no notice to or filing with, any governmental authority or regulatory body or any other third party is required for the due execution, delivery or performance by the Company of any Opinion Document to which it is a party or, if any such authorization, approval, consent, action, notice or filing is required, it has been duly obtained, taken, given or made and is in full force and effect.

2

We have not independently established the validity of the foregoing assumptions.

“Generally Applicable Law” means the federal law of the United States of America, and the law of the State of New York (including the rules and regulations promulgated thereunder or pursuant thereto), that a New York lawyer exercising customary professional diligence would reasonably be expected to recognize as being applicable to the Company, the Opinion Documents or the transactions governed by the Opinion Documents, and for purposes of assumption paragraph (f) above and our opinion below, the General Corporation Law of the State of Delaware. Without limiting the generality of the foregoing definition of Generally Applicable Law, the term “Generally Applicable Law” does not include any law, rule or regulation that is applicable to the Company, the Opinion Documents or such transactions solely because such law, rule or regulation is part of a regulatory regime applicable to the specific assets or business of any party to any of the Opinion Documents or any of its affiliates.

Based upon the foregoing and upon such other investigation as we have deemed necessary and subject to the assumptions and qualifications set forth herein, we are of the opinion that the Notes have been duly authorized by the Company and, when authenticated by the Trustee in accordance with the terms of the Indenture and delivered to and paid for as provided in the Underwriting Agreement, will be the legal, valid and binding obligations of the Company, enforceable against the Company in accordance with their terms and entitled to the benefits of the Indenture.

Our opinion expressed above is subject to the effect of (a) any applicable bankruptcy, insolvency, reorganization, moratorium or similar laws affecting creditors’ rights generally (including without limitation all laws relating to fraudulent transfers) and (b) general principles of equity, including without limitation concepts of materiality, reasonableness, good faith and fair dealing (regardless of whether considered in a proceeding in equity or at law).

Our opinion is limited to Generally Applicable Law, and we do not express any opinion herein concerning any other law.

This opinion letter is rendered to you in connection with the Registration Statement on Form S-3ASR (File No. 333-182222) relating to the Notes (the “Registration Statement”) filed by the Company under the Securities Act of 1933, as amended (the “Securities Act”).

This opinion letter speaks only as of the date hereof. We expressly disclaim any responsibility to advise you of any development or circumstance of any kind, including any change of law or fact, that may occur after the date of this opinion letter that might affect the opinion expressed herein.

3

We hereby consent to the filing of this opinion letter as an exhibit to the Current Report on Form 8-K dated the date hereof filed by the Company and incorporated by reference into the Registration Statement and to the use of our name under the heading “Legal Matters” in the prospectus constituting a part of such Registration Statement. In giving this consent, we do not hereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Securities and Exchange Commission promulgated thereunder.

RCT/HH/CCD/TA

STG

4