- 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 May 2011

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 the provisions of article 12, paragraph 6, of CVM Instruction No. 358/02, communicates that it has received a notice from Capital Group International, Inc. (“Capital Group”), in its role as the holding company of investment management companies abroad, with the following information:

“In compliance with article 12, preamble, of CVM Instruction No. 358, dated January 3, 2002, as amended, Capital Group International, Inc., an entity existing under the laws of the United States of America, with headquarters at 333, South Hope Street, Los Angeles, California 90071, United States of America (“CGII”), in its role as the holding company of investment management companies abroad, discloses that, through stock market transactions that took place today on behalf of its clients, it acquired preferred shares (“Preferred Shares”) or American Depositary Receipts (“ADRs”) representing preferred shares, issued by Tele Norte Leste Participações S.A., publicly-held company, registered in the corporate taxpayers’ registry (CNPJ/MF) under No. 02.558.134/0001-58 (the “Company”). As of May 9, 2011, CGII managed 15,084,413 Preferred Shares, corresponding to 5.20% of this type of share and, as a result of the above-mentioned transactions, it now manages a total of 31,410,209 Preferred Shares, corresponding to 10.84% of this type of share. In addition to the participation in the Company described above, Capital Research and Management Company, a member of the same economic group as CGII, in its role as manager of investments abroad, manages 6,225,195 Preferred Shares issued by the Company, corresponding to 2.14%. This is a minority investment that does not alter the control or administrative structure of the Company. At present, CGII does not envision a target number of Company shares to acquire. Neither CGII nor any person affiliated with it holds, directly or indirectly, any debentures convertible into shares, and neither CGII nor any person affiliated with it is a party to any agreement or contract regulating the exercise of voting rights or the purchase and sale of securities issued by the Company. May 26, 2011. CAPITAL GROUP INTERNATIONAL, INC.”

Rio de Janeiro, May 27, 2011.

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: May 27, 2011