Table of Contents

  6

SCHEDULE 13D

Item 1. Security and Issuer.

     This Statement on Schedule 13D relates to the preferred shares, no par value (ações preferenciais), of Telesp Celular Participações S.A., a corporation organized under the laws of the Federative Republic of Brazil, or TCP. The address of the principal executive office of TCP is Avenida Roque Petroni Júnior, 1464 — Morumbi, 04707-000 São Paulo, SP, Brazil, and the company’s phone number is (55) 11-5105-1207.

     The entities identified on the cover pages of this Schedule 13D (collectively, the “Reporting Persons”) have not previously filed a Statement on Schedule 13D with respect to the preferred shares of TCP because those preferred shares are generally non-voting securities for purposes of Rule 13d-1(i) under the Securities Exchange Act of 1934, as amended, or the Exchange Act. However, TCP’s bylaws state that holders of preferred shares will have full voting rights in the event that TCP does not pay minimum dividends to those shareholders for three consecutive fiscal years, and those shareholders will retain those voting rights until TCP again pays minimum dividends. Because TCP did not pay minimum dividends for the years ended December 31, 2001, 2002 and 2003, holders of TCP preferred shares have been able to exercise voting rights since March 26, 2004, the date of TCP’s 2004 general shareholders’ meeting.

     The Reporting Persons recently became aware that a Schedule 13D may be required in these circumstances, as the preferred shares now have voting rights, and are hereby satisfying that requirement.

Item 2. Identity and Background.

     This Schedule 13D is being filed jointly by the Reporting Persons. The agreement among the Reporting Persons relating to the joint filing of this Schedule 13D is attached as Exhibit 1 hereto.

     Brasilcel. Brasilcel N.V., or Brasilcel, is a joint venture of Telefónica Móviles, S.A., or Telefónica Móviles; on the one hand, and Portugal Telecom and PT Móveis, on the other hand, and is managed on an equal basis by those companies. Brasilcel was created pursuant to a strategic agreement signed by Portugal Telecom and Telefónica Móviles in January 2001 to create a cellular services company in Brazil that would aggregate all of the parties’ investments in cellular telecommunications businesses in Brazil to the extent permitted under Brazilian law. See Items 3 and 6. Brasilcel is incorporated under the laws of The Netherlands. Its corporate domicile is located at Strawinskylaan, 3105, 1077 ZX, Amsterdam, The Netherlands.

     Portelcom Participações. Portelcom Participações S.A., or Portelcom Participações, is incorporated under the laws of Brazil. The principal business of Portelcom Participações is as a holding company for a portion of Brasilcel’s investment in TCP. Its principal executive offices are located at Av. Brigadeiro Faria Lima, 2277, 15th Floor, Suite 1503, 01452-000 São Paulo, SP, Brazil. Its telephone number is (55) 11 3039-8016.

     Portugal Telecom. Portugal Telecom, SGPS, S.A., or Portugal Telecom, is a limited liability holding company organized under the laws of the Republic of Portugal. The principal business of Portugal Telecom is, through its subsidiaries, the provision of wireless services, including fixed lines, data and business solutions and internet related services; cellular telecommunications services in Portugal and Brazil, multimedia services including TV programming, film distribution and screening, newspaper publishing and distribution, radio programming and provisioning of Cable Internet; and sale of telecommunication equipment. Its principal executive offices are located at Avenida Fontes Pereira de Melo, 40, 1069-300, Lisbon, Portugal. Its telephone number is (351) 21 500-1701.

     PT Móveis. PT Móveis, SGPS, S.A., or PT Móveis, is a limited liability holding company organized under the laws of the Republic of Portugal. PT Móveis is a subsidiary of TMN. The principal business of PT Móveis is as a holding company for Portugal Telecom’s investment in Brasilcel and in Medi Telecom, which provides cellular telecommunications services in Morocco. Its principal executive offices are located at Avenida Álvaro Pais, 02, 1649-041, Lisbon, Portugal. Its telephone number is (351) 21 791-4400.

  7

     TMN. TMN — Telecomunicações Móveis Nacionais S.A., or TMN, is a limited liability holding company, organized as a Sociedade Anónima under the laws of the Republic of Portugal. TMN is a wholly owned subsidiary of Portugal Telecom. The principal business of TMN is the provision of cellular telecommunications services in Portugal. Its principal executive offices are located at Avenida Álvaro Pais, 02, 1649-041 Lisbon, Portugal. Its telephone number is (351) 21 791-4400.

     Schedule 1 hereto sets for the (a) name, (b) residence or business address, (c) principal occupation or employment and (d) citizenship of each of the directors and executive officers of the Reporting Persons.

     During the last five years, none of the Reporting Persons or, to the knowledge of the Reporting Persons, any of the persons listed on Schedule 1 hereto has been (1) convicted in a criminal proceeding (excluding traffic violations or similar misdemeanors) or (2) a party to a civil proceeding of a judicial or administrative body of competent jurisdiction and as a result of such proceeding has been or is subject to a judgment, decree or final order enjoining future violations of, or prohibiting or mandating activities subject to, federal or state securities laws or finding any violation with respect to such laws.

Item 3. Source and Amount of Funds or Other Consideration.

     This Schedule 13D is not being filed due to a recent purchase of preferred shares of TCP by the Reporting Persons. Rather, as explained in response to Item 1, this Schedule 13D is being filed because the preferred shares recently received voting rights as a result of the non-payment by TCP of minimum dividends for the years ended December 31, 2001, 2002 and 2003. All purchases of preferred shares and their related sources and amounts of funds occurred prior to the existence of any reporting requirement as to the Schedule 13D. The following describes the background of these purchases.

     In 1998, in preparation for the restructuring and privatization of Telebrás and its operating subsidiaries, collectively known as the Telebrás System, the cellular telecommunications operations of the Telebrás System were spun off into separate companies. TCP was one of 12 new holding companies created. In connection with the reorganization of the Telebrás System, TCP was allocated all of the share capital held by Telebrás in Telesp Celular S.A., or Telesp Celular, one of the cellular operating companies that provided cellular telecommunications service in the state of São Paulo, Brazil. In July 1998, as part of its restructuring and privatization plan, the Brazilian federal government sold substantially all of its common shares of the new holding companies, including TCP, to private sector buyers.

     Portelcom Participações acquired 51.8% of the common shares of TCP from the Brazilian federal government in the privatization. At the time, Portugal Telecom owned 64.2% of Portelcom Participações, and Telefónica Internacional, S.A. owned the remaining 35.8%. Portelcom Participações’s interest in TCP represented a 10.0% economic interest in, and voting control of, Telesp Celular (8.8% of which was acquired in the privatization of the Telebrás System and the remaining 1.2% of which was acquired with the proceeds of shares previously acquired in the Telebrás System). Forty percent of the purchase price of TCP was paid in 1998, and the remaining purchase price was financed with a loan from Banco Nacional de Desenvolvimento Econômico e Social — BNDES, the Brazilian national development bank. In January 1999, Portugal Telecom prepaid the loan to BNDES.

     In January 2000, all shares of Telesp Celular owned by shareholders other than TCP, were exchanged for newly issued shares of TCP, and Telesp Celular became a wholly owned subsidiary of TCP. In June 2000, Portugal Telecom conducted a cash tender offer in Brazil for ordinary shares in TCP. As a result of the tender offer, Portugal Telecom increased its economic interest in TCP to 29.9%. In November 2000, TCP completed a capital increase in which Portugal Telecom subscribed for additional shares in TCP, and, upon acquisition of such shares, Portugal Telecom’s economic interest in TCP increased to 36.2%, corresponding to 83.6% of TCP’s common shares and 17.7% of its preferred shares. In November 2000, Portugal Telecom exchanged with Telefónica, S.A., or Telefónica, its minority interest in Telecomunicações de São Paulo S.A. — TELESP (a fixed line telecommunications operator in the state of São Paulo controlled by Telefónica) for an additional interest in TCP, increasing its economic interest in TCP to 41.2%, corresponding to 85.1% of TCP’s common shares and 17.7% of its preferred shares.

     In September 2002, TCP completed a rights offering in which Portugal Telecom subscribed for a total of 247,224 million common shares and 326,831 million preferred shares, thereby increasing its economic interest in TCP to

  8

65.1%, corresponding to 93.7% of TCP’s common shares and 49.8% of its preferred shares. In October 2002, in connection with the joint agreement with Telefónica Móviles (the cellular telecommunications subsidiary of Telefónica), that created Brasilcel (which has operated under the brand name Vivo since April 2003), Portugal Telecom sold 172,016,089,469 preferred shares, or 22.6% of TCP’s preferred shares (corresponding to 14.7% of TCP’s total share capital), to Telefónica Móviles. On December 27, 2002, Portugal Telecom contributed the remainder of its interest in TCP to Brasilcel.

Item 4. Purpose of the Transaction.

     The purpose of the original acquisition of shares of TCP and, indirectly, of Telesp Celular was to enter the market for the provision of cellular telecommunications services in the state of São Paulo and in Brazil generally. The purpose of the subsequent tender offers for shares of TCP was to increase Portugal Telecom’s economic interest in TCP and, indirectly, in Telesp Celular. The purpose of the contribution by Portugal Telecom and Telefónica Móviles of their interests in various cellular telecommunications companies in Brazil, including TCP, to Brasilcel, was to create the leading cellular telecommunications operator in Brazil. On October 8, 2004, TCP announced a capital increase in an amount of up to R$2,054 million, to be effected through offerings of preemptive rights to subscribe for common shares and preferred shares of TCP. On October 12, 2004, TCP filed a Registration Statement on Form F-3 with the Securities and Exchange Commission relating to the rights offering to holders of TCP preferred shares and American Depositary Shares representing TCP preferred shares. Brasilcel and Portelcom Participações have indicated that, depending on market conditions, they intend to subscribe fully for all of the common shares and preferred shares to which they are entitled in the rights offerings. Brasilcel and Portelcom Participações have also indicated that, depending on market conditions, they intend to subscribe for any remaining common shares and preferred shares to which they are entitled in the reoffering rounds of the rights offerings and may purchase additional common shares and preferred shares in any public auction at the São Paulo Stock Exchange that may be held with respect to shares that remain unsubscribed after the reoffering rounds. Through any such purchases, the percentage of TCP’s preferred shares beneficially owned by the Reporting Persons may increase. Neither Brasilcel nor Portelcom Participações is obligated to purchase any shares, and they may determine not to do so.

Item 5. Interest in Securities of the Issuer.

     (a) Each of Brasilcel, Portugal Telecom, TMN and PT Móveis may be deemed to be beneficial owners pursuant to the Exchange Act of the 379,614,824,965 preferred shares of TCP, or 49.8% of TCP’s outstanding preferred shares, held directly by Brasilcel. Each of Brasilcel, Portugal Telecom, TMN, PT Móveis and Portelcom Participações may be deemed to be beneficial owners pursuant to the Exchange Act of the 719,908 preferred shares of TCP held directly by Portelcom Participações. Telefónica and Telefónica Móviles may be deemed to be beneficial owners pursuant to the Exchange Act of the shares of TCP held by Brasilcel and Portelcom Participações and may be deemed, together with Portugal Telecom, TMN, PT Móveis, Brasilcel and Portelcom, to comprise a group within the meaning of Section 13(d)(3) of the Exchange Act. However, the Reporting Persons disclaim membership in a group within the meaning of Section 13(d)(3) of the Exchange Act. To the knowledge of the Reporting Persons, none of the persons listed on Schedule 1 hereto beneficially owns any preferred shares of TCP.

     (b) Brasilcel has sole power to vote or to dispose of the preferred shares of TCP it holds directly. Portelcom Participações and its parent Brasilcel each may be deemed to have sole power to vote or to dispose of preferred shares of TCP held directly by Portelcom Participações. Pursuant to the joint venture arrangement described in Item 6, Portugal Telecom and PT Móveis, on one hand, and Telefónica Móviles, on the other hand, have equal voting rights in Brasilcel. Portugal Telecom, TMN and PT Móveis (which is a wholly owned subsidiary of TMN) therefore each may be deemed to share the power to vote or to dispose of preferred shares of TCP held directly and indirectly by Brasilcel.

     (c) None of the Reporting Persons has effected any transaction in the preferred shares of TCP in the past 60 days. To the knowledge of the Reporting Persons, none of the persons listed on Schedule 1 hereto has effected any transactions in the common shares or preferred shares of TCP in the past 60 days.

     (d) No person other than the Reporting Persons is known to have the right to receive or the power to direct the receipt of the dividends from, or the proceeds from the sale of the preferred shares of TCP held directly and indirectly by Brasilcel, except for the rights and powers of Telefónica Móviles under the joint venture arrangement described in Item 6 and the rights and powers of Telefónica as the controlling shareholder of Telefónica Móviles.

     (e) Not applicable.

  9

Item 6. Contracts, Arrangements, Understandings or Relationships with Respect to Securities of the Issuer.

   Joint Venture Arrangement

     On January 23, 2001, Telefónica Móviles, Portugal Telecom and PT Móveis agreed to create a joint venture to consolidate Telefónica Móviles’ cellular businesses in Brazil with those of Portugal Telecom. Under this joint venture framework agreement, each of the Telefónica group and the Portugal Telecom group agreed to contribute to a 50:50 joint venture certain of its cellular businesses in Brazil, including interests in operating companies and holding companies that own cellular licenses in Brazil, such as TCP, as well as other assets or business that are operated for the benefit of those companies. This joint venture resulted in the formation of Brasilcel, the controlling shareholder of TCP.

     On October 17, 2002, Telefónica Móviles, on the one hand, and Portugal Telecom and PT Móveis, on the other, entered into the definitive stockholders’ agreement and subscription agreement that implemented the joint venture framework agreement signed in January 2001. In accordance with these definitive agreements, Telefónica Móviles and the Portugal Telecom group have the same voting rights in Brasilcel. This equality in voting rights will continue to exist even if either party’s economic and voting interest is diluted below 50%, but not lower than 40%, as a consequence of a capital increase. The equality in voting rights will cease to exist if the percentage of ownership of one of the parties falls below 40% during an uninterrupted period of six months. In this event, if the group with the reduced interest were the Portugal Telecom Group, it would be entitled to sell to Telefónica Móviles, which would be obliged to buy (directly or through another company), all of Portugal Telecom’s ownership interest in Brasilcel. This right expires on December 31, 2007. This put option would be exercisable in the 12 months subsequent to the end of the aforementioned six-month period, provided that the Portugal Telecom group had not increased its ownership interest to 50% of the total capital stock of Brasilcel.

     Also, in accordance with the definitive agreements, the Portugal Telecom group would be entitled to sell to Telefónica Móviles, which would be obligated to buy, all of Portugal Telecom’s ownership interest in Brasilcel should there be a change in control at Telefónica, Telefónica Móviles or any subsidiary of the latter that holds a direct or indirect ownership interest in Brasilcel. Similarly, Telefónica Móviles would be entitled to sell to the Portugal Telecom group, which would be obliged to buy, its ownership interest in Brasilcel if there is a change of control at Portugal Telecom, PT Móveis or any other subsidiary of either company that holds a direct or indirect ownership interest in Brasilcel.

     The definitive agreements established that the parties to the agreements shall transfer to Brasilcel all of their direct or indirect ownership interests in equity securities, whether voting or non-voting, in cellular properties in Brazil, including any such interests obtained from future acquisitions of Brazilian cellular properties by those parties.

     On December 27, 2002, following the agreements entered into on October 17, 2002 and after having obtained the necessary authorization from the Brazilian authorities for the contribution, Telefónica Móviles and PT Moveis contributed to Brasilcel all the shares held directly or indirectly by the two groups in their cellular communications companies in Brazil.

   Floating Rate Notes

   TCP had outstanding indebtedness to Portugal Telecom International Finance B.V., a company in the Portugal Telecom group, evidenced by floating rate notes, in the amount of €416.05 million at June 30, 2004 (representing R$1.58 billion at that date) that bears interest quarterly at EURIBOR plus 7% per annum and matures in November 2004.

  10

Item 7. Material to be Filed as Exhibits.

SIGNATURE

     After reasonable inquiry and to the best of my knowledge and belief, I certify that the information set forth in this statement is true, complete and correct.

Dated: October 12, 2004

[Signature Page to Schedule 13D]

Dated: October 12, 2004

[Signature Page to Schedule 13D]

Dated: October 12, 2004

[Signature Page to Schedule 13D]

Dated: October 12, 2004

[Signature Page to Schedule 13D]

Dated: October 12, 2004

[Signature Page to Schedule 13D]

SCHEDULE 1

DIRECTORS AND EXECUTIVE OFFICERS OF THE REPORTING PERSONS

BRASILCEL N.V.

1

2

3

4

5

6

7

8

EXHIBIT INDEX