Opinion of Cleary, Gottlieb, Steen & Hamilton with respect to the new notes.

We have acted as your special United States counsel in connection with the Registration Statement on Form F-4 (the “Registration Statement”) filed on the date hereof by Vale Overseas Limited, a Cayman Islands exempted company incorporated with limited liability (the “Company”) and Companhia Vale do Rio Doce, a Brazilian corporation, as guarantor (the “Guarantor”) with the United States Securities and Exchange Commission (the “Commission”) pursuant to the Securities Act of 1933, as amended (the “Securities Act”), in connection with the proposed offer to exchange (the “Exchange Offer”) up to U.S.$300,000,000 of the Company’s Series B 9.0% Guaranteed Notes due 2013 (the “New Notes”) that have been registered under the Securities Act for an equal principal amount of the Company’s outstanding Series A 9.0% Guaranteed Notes due 2013 (the “Old Notes”). The New Notes will be issued under an indenture dated as of March 8, 2002 (the “Original Indenture”) as supplemented by a second supplemental indenture thereto dated as of August 8, 2003 among the Company, the Guarantor and JPMorgan Chase Bank, as trustee (the “Supplemental Indenture” and, together with the Original Indenture, the “Indenture”). Pursuant to the Indenture, the Guarantor will unconditionally guarantee (the “Guarantee”) all of the Company’s obligations under the New Notes.

In arriving at the opinions expressed below, we have reviewed the following documents:

(b) executed copies of the Original Indenture and the Supplemental Indenture; and

In addition, we have reviewed originals or copies certified or otherwise identified to our satisfaction of all such corporate records of the Company and the Guarantor and such other instruments and other certificates of public officials, officers and representatives of the Company and the Guarantor and such other persons, and we have made such investigations of law, as we have deemed appropriate as a basis for the opinions expressed below.

In rendering the opinions expressed below, we have assumed the authenticity of all documents submitted to us as originals and the conformity to the originals of all documents submitted to us as copies. In addition, we have assumed and have not verified (i) the accuracy as to factual matters of each document we have reviewed and (ii) that the New Notes and the Guarantee conform to the form thereof that we have reviewed and will be duly authenticated in accordance with the terms of the Indenture.

Based on the foregoing, and subject to the further assumptions and qualifications set forth below, it is our opinion that when the New Notes and the Guarantee, in the form filed as Exhibit 4.3 to the Registration Statement, have been duly executed by the Company and the Guarantor and authenticated by the Trustee in accordance with the Indenture, and duly issued and delivered on consummation of the Exchange Offer in exchange for an equal principal amount of Old Notes (a) the New Notes will be the valid, binding and enforceable obligations of the Company, entitled to the benefits of the Indenture and (b) the Guarantee of the New Notes will be a valid, binding and enforceable obligation of the Guarantor, entitled to the benefits of the Indenture.

Insofar as the foregoing opinions relate to the validity, binding effect or enforceability of any agreement or obligation of the Company or the Guarantor, (a) we have assumed that the Company and the Guarantor and each other party to such agreement or obligation has satisfied those legal requirements that are applicable to it to the extent necessary to make such agreement or obligation enforceable against it (except that no such assumption is made as to the Company and the Guarantor regarding matters of the federal law of the United States of America or the law of the State of New York) and (b) such opinions are subject to applicable bankruptcy, insolvency and similar laws affecting creditors’ rights generally, to judicial application of foreign laws or foreign governmental actions affecting creditors’ rights and to general principles of equity.

We express no opinion as to the enforceability of Section 10.8 of the Indenture providing for indemnification by the Company and the Guarantor of the Trustee and the holders of securities issued under the Indenture against any loss in obtaining the currency due to the Trustee or such holders under the Indenture from a court judgment in another currency.

In addition, we note that the waiver of defenses relating to the Guarantee in Article 12 of the Indenture may be ineffective to the extent that any such defense involves a matter of public policy in New York (such as reflected in New York’s anti-champerty statute).

The foregoing opinions are limited to the federal law of the United States of America and the law of the State of New York.

We hereby consent to the filing of this opinion as Exhibit 5.1 to the Registration Statement and to the reference to this firm in the Registration Statement and the related prospectus under the headings “Validity of the New Notes” and “Certain Tax Consequences of the Exchange Offer.” In giving such 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 Commission thereunder.

Very truly yours, CLEARY, GOTTLIEB, STEEN & HAMILTON

By:		/S/ NICOLAS GRABAR

		Nicolas Grabar, a Partner