FILED PURSUANT TO RULE 425

Filed by: Tele Norte Leste Participações S.A.
Pursuant to Rule 425 under the Securities Act of 1933
Subject Company: Telemar Participações S.A.
Registration Nos. 333-133992 and 333-133994

This Statement of Material Fact is not an offer for sale of the securities in the United States. Any security referred to in this Statement of Material Fact may not be sold in the United States absent registration or an exemption from registration. Any public offering of the securities mentioned in this Statement of Material Fact will be made by means of a prospectus containing detailed information regarding the Telemar Participações S.A., Tele Norte Leste Participações S.A. and their management, as well as financial statements. All securities issued or sold as part of the corporate restructuring or the secondary public offering will be registered in the United States unless an exemption from registration is available.


Tele Norte Leste		Telemar Norte
Participações S.A.		Leste S.A.
Corporate Taxpayer Registration (CNPJ/MF)		Corporate Taxpayer Registration (CNPJ/MF)
no. 02.558.134/0001-58		no. 33.000.118/0001-79
Business Registration (NIRE)		Business Registration (NIRE)
no. 33 3 0026253 9		no. 33 300 152 580
A Publicly-Traded Company		A Publicly-Traded Company

Telemar
Participações S.A.
Corporate Taxpayer Registration (CNPJ/MF) no. 02.107.946/0001-87
Business Registration (NIRE)
no. 3330016601-7
Publicly-Traded Company

STATEMENT OF MATERIAL FACT

Further to the Statements of Material Fact released on April 17, 2006 and May 11, 2006, Telemar Participações (“TmarPart”), Tele Norte Leste Participações (“TNLP”, Bovespa: TNLP3, TNLP4; NYSE: TNE) and Telemar Norte Leste (“Tmar”, Bovespa: TMAR3, TMAR5, TMAR6), referred to collectively as the “Telemar Companies”, inform their shareholders and the market in general of the following:

1. TmarPart has received comments and requests for additional information from the São Paulo Stock Exchange (“Bovespa”), the Brazilian Securities Commission (Comissão de Valores Mobiliários — “CVM”) and the U.S. Securities and Exchange Commission (“SEC”) in connection with the Corporate Stock Swap transaction and secondary public offering of shares by TmarPart’s controlling shareholders, as disclosed in the earlier Statements of Material Fact, referred to above.

2. The Telemar Companies’ managements are working to respond to the requests issued by Bovespa, the CVM and the SEC.

3. When the requests referred in item 1 above have been complied with and, consequently, the Registration Statement on Form F-4 is declared effective by the SEC, TNLP will call the General Meeting of TNLP Shareholders, according to items 4.1.1 and 4.1.2 of Statement of Material Fact disclosed on April 17^th, 2006. TNLP General Shareholders Meeting is expected to occur during the month of July, 2006. Concomitantly, TNLP’s shareholders who hold American Depositary Receipts (“ADRs”) will be contacted by the depositary bank with respect to exercise of the vote at the General Meeting of TNLP Shareholders referred to above.

4. Once the General Meeting of TNLP Shareholders is held and assuming the Corporate Stock Swap is approved, TmarPart’s and TNLP’s managements intend to start taking the complementary procedures required in order to effect the secondary public offering.

5. The Telemar Companies have submitted to the Brazilian Telecommunications Agency (Agência Nacional de Telecomunicações — Anatel) an application for authorization to implement the Corporate Reorganization, and Anatel’s response is expected within the next few weeks.

6. In view of foregoing, the managements of TmarPart and TNLP consider it advisable to adjust the “Estimated Time Periods” disclosed in the earlier Statements of Material Fact, such that the secondary public offer and the Corporate Reorganization are expected to be concluded at the second semester of this year.

7. Management of the Telemar Companies will publish other statements of material fact as and when new events arise or the conditions for implementing the transactions referred to herein are fulfilled.

Rio de Janeiro, June 16, 2006.

TELE NORTE LESTE PARTICIPAÇÕES S.A.

TELEMAR NORTE LESTE S.A.

TELEMAR PARTICIPAÇÕES S.A.