- 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 ^o 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 300 26253-9

Publicly-Held Company

NOTICE TO DEBENTURE HOLDERS OF THE THIRD ISSUANCE OF TELE NORTE LESTE PARTICIPAÇÕES S.A.

EARLY REDEMPTION

Tele Norte Leste Participações S.A. (the “Issuer”) informs the Debenture Holders of the third public issuance of unsecured debentures, not convertible into shares (“Debenture Holders”), in accordance with Clause 6.13 of the Indenture of the third public issuance of unsecured debentures, not convertible into shares of Tele Norte Leste Participações S.A. that on March 28, 2012 , it will call for the early redemption of all of the outstanding single-series Debentures. Consequently, the Debentures will be cancelled and payment of the face value of the outstanding single-series Debentures of the single series, plus applicable interest, as the case may be, without premium, calculated in accordance with the terms of the above-referenced Indenture, will be made.

Rio de Janeiro, March 12, 2012.

Alex Waldemar Zornig

Investor Relations Officer

TELE NORTE LESTE PARTICIPAÇÕES S.A.

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 12, 2012