- Report of Foreign Issuer (6-K)

UNITED STATES

SECURITIES AND EXCHANGE COMMISSION

Washington, D.C. 20549

FORM 6-K

Report of Foreign Private Issuer

Pursuant to Rule 13a-16 or 15d-16 of

the Securities Exchange Act of 1934

For the month of March 2012

Commission File Number: 001-14487

TELE NORTE LESTE PARTICIPAÇÕES S.A.

(Exact Name as Specified in its Charter)

Tele Norte Leste Holding Company

(Translation of registrant’s name into English)

Rua Humberto de Campos, 425 – 8° andar

22430-190 Rio de Janeiro, RJ

Federative Republic of Brazil

(Address of principal executive offices)

(Indicate by check mark whether the registrant files or will file annual reports under cover of Form 20-F or Form 40-F.)

Form 20-F: x Form 40-F: ¨

(Indicate by check mark if the registrant is submitting the Form 6-K in paper as permitted by Regulation S-T Rule 101(b)(1)):

Yes : ¨ No : x

(Indicate by check mark if the registrant is submitting the Form 6-K in paper as permitted by Regulation S-T Rule 101(b)(7)):

Yes : ¨ No : x

(Indicate by check mark whether the registrant by furnishing the information contained in this Form, the Registrant is also thereby furnishing the information to the Commission pursuant to Rule 12g3-2(b) under the Securities Exchange Act of 1934.)

Yes : ¨ No : x

If “Yes” is marked, indicate below the file number assigned to the registrant in connection with Rule 12g3-2(b):

LOGO

TELE NORTE LESTE PARTICIPAÇÕES S.A.

Corporate Taxpayers’ Registry (CNPJ/MF) No. 02.558.134/0001-58

Board of Trade (NIRE) No. 33 3 0026253 9

Publicly-Held Company

NOTICE TO THE MARKET

Tele Norte Leste Participações S.A. (“TNL” or the “Company”), in compliance with article 12 of CVM Instruction No. 358/02, communicates that it has received a correspondence from The Bank of New York Mellon Corporation, acting in its own name and in representation of its subsidiaries, with the following information:

“Dear Sirs,

In compliance with article 12 of CVM Instruction No. 358, dated January 3, 2002, as amended, (“ Instruction 358 ”), The Bank of New York Mellon Corporation , an entity existing under the laws of the United States of America, with headquarters at One Wall Street, New York, NY 10286 USA, hereinafter “ BNY Mellon ”; BNY Mellon ARX Investimentos Ltda. (“ Subsidiary 1 ”), an entity existing under the laws of Brazil, registered in the corporate taxpayers’ registry (CNPJ/MF) under No. 04.408.128/0001-40, with headquarters at Avenida Borges de Medeiros, No. 633, 4 ^th floor, Rio de Janeiro, Brazil; The Boston Company Asset Management (“ Subsidiary 2 ”), an entity existing under the laws of the United States of America, with headquarters at One Boston Place, 14 ^th Floor, Boston, Massachusetts, 02108 USA; Mellon Capital Management Corporation (“ Subsidiary 3 ”), an entity existing under the laws of the United States of America, with headquarters at 50 Fremont Street, Suite 3900, San Francisco, CA 94105 USA; Newton Investment Management Limited (“ Subsidiary 4 ”), an entity existing under the laws of the United Kingdom, with headquarters at The Bank of New York Mellon Financial Centre, 160 Queen Victoria Street, London EC4V 4LA, England; MBSC Securities Corporation (“ Subsidiary 5 ”), an entity existing under the laws of the United States of America, with headquarters at 200 Park Avenue, New York, NY 10166 USA; The Bank of New York Mellon Trust Company, National Association (“ Subsidiary 6 ”), an entity existing under the laws of the United States of America, with headquarters at One Mellon Center, 500 Grant street, Pittsburgh, Pennsylvania 15258 USA; and Pershing LLC (“ Subsidiary 7 ”), an entity existing under the laws of the

United States of America, with headquarters at One Pershing Plaza, Jersey City, New Jersey 07399 USA, (Subsidiaries 1, 2, 3, 4, 5, 6 and 7, being subsidiaries of BNY Mellon , will hereinafter be referred to collectively as the “ Subsidiaries ”), hereby provide the following information:

On February 27, 2012 , (the “ Base Date ”), BNY Mellon, through its Subsidiaries, acting as managers of investment funds, in a discretionary and independent manner, reduced its indirect participation, and now holds 13,927,306 (thirteen million, nine hundred twenty-seven thousand, three hundred six) preferred shares of the share capital of Tele Norte Leste Participações S.A. (the “ Company ”) representing, approximately, 4.81% (four and eight-one hundredths percent) of the preferred shares issued by the Company.

This reduction is the result of the sale, on the Base Date, of 1,273,034 (one million, two hundred seventy-three thousand, thirty-four) preferred shares issued by the Company, by investment funds managed by the Subsidiaries;

Prior to the referred to Base Date, BNY Mellon held, indirectly , 15,200,340 (fifteen million, two hundred thousand, three hundred forty) preferred shares issued by the Company, which were held by investment funds managed by the Subsidiaries.

Such that, on the Base Date, the indirect participation of BNY Mellon was reduced to less than the limit 5% (five percent) established by Instruction 358.

Furthermore, BNY Mellon and its Subsidiaries declare:

(i) that the acquisition of shares is exclusively for investment purposes, and not in order to alter the control or administrative structure of the Company;

(ii) that they are not parties to any agreement or contact regulating the exercise of voting rights or the purchase and sale of securities issued by the Company;

(iii) not to hold any warrants, rights to subscribe for shares, options to purchase shares or debentures convertible into shares issued by the Company.

If you have questions or need any clarification, please contact Nicholas Darrow at 412-236-7733.

THE BANK OF NEW YORK MELLON CORPORATION



Nicholas R. Darrow
Mr. Vice President”

Rio de Janeiro, March 14, 2012.

Alex Waldemar Zornig

Investor Relations Officer

SIGNATURES

Pursuant to the requirements of the Securities Exchange Act of 1934, the registrant has duly caused this report to be signed on its behalf by the undersigned, thereunto duly authorized.

Date: March 14, 2012