Exhibit 5.1

[LETTERHEAD OF SIDLEY AUSTIN BROWN & WOOD LLP]

May 7, 2004

R. R. Donnelley & Sons Company

77 West Wacker Drive

Chicago, Illinois 60601

Re: 10,620,451 Shares of Common Stock, Par Value $1.25 Per Share, and

10,620,451 Preferred Stock Purchase Rights Associated Therewith

Ladies and Gentlemen:

We refer to the Registration Statement on Form S-3 (the “Registration Statement”) being filed by R. R. Donnelley & Sons Company, a Delaware corporation (the “Company”), with the Securities and Exchange Commission (the “SEC”) under the Securities Act of 1933, as amended (the “Securities Act”), relating to the registration of 10,620,451 shares of common stock, par value $1.25 per share (the “Registered Shares”), of the Company, together with 10,620,451 preferred stock purchase rights (the “Rights”) associated therewith, which may be sold by certain stockholders of the Company. The terms of the Rights are set forth in the Rights Agreement, dated as of April 25, 1996 (the “Rights Agreement”), between the Company and EquiServe Trust Company, N.A., as successor to First Chicago Trust Company of New York, as rights agent.

In rendering this letter, we have examined and relied upon a copy of the Registration Statement and the exhibits filed therewith. We have also examined originals, or copies of originals certified to our satisfaction, of such agreements, documents, certificates and statements of government officials and other instruments, and have examined such questions of law and have satisfied ourselves as to such matters of fact, as we have considered relevant and necessary as a basis for this letter. We have assumed the authenticity of all documents submitted to us as originals, the genuineness of all signatures, the legal capacity of all natural persons and the conformity with the original documents of any copies thereof submitted to us for examination.

Based on the foregoing, and subject to the qualifications and limitations hereinafter set forth, we are of the opinion that:

1. The Company is a duly incorporated and validly existing corporation under the laws of the State of Delaware.

SIDLEY AUSTIN BROWN & WOOD LLP CHICAGO

R. R. Donnelley & Sons Company

May 7, 2004

Page 2

2. Each Registered Share that is covered by the Registration Statement has been legally issued, fully paid and nonassessable.

3. Each Right associated with each Registered Share has been legally issued.

This letter is limited to the General Corporation Law of the State of Delaware.

We hereby consent to the filing of this letter as Exhibit 5.1 to the Registration Statement and to all references to our Firm included in or made a part of the Registration Statement. In giving such consent, we do not thereby admit that we are within the category of persons for whom consent is required by Section 7 of the Securities Act or the related rules promulgated by the SEC thereunder.

Very truly yours,

/S/    SIDLEY AUSTIN BROWN & WOOD LLP