================================================================================

                                    FORM 6-K
                       SECURITIES AND EXCHANGE COMMISSION
                             Washington, D.C. 20549

                            Report of Foreign Issuer

                      Pursuant to Rule 13a-16 or 15d-16 of
                       the Securities Exchange Act of 1934

                          For the month of March, 2003

                        Commission File Number: 001-14485

                      TELE SUDESTE CELLULAR HOLDING COMPANY
                 (Translation of registrant's name into English)

                        Praia de Botafogo, 501, 7o andar
                      22250-040 Rio de Janeiro, RJ, Brazil
                     (Address of principal executive office)

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 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): N/A
                                ----

================================================================================




                     TELE SUDESTE CELLULAR HOLDING COMPANY

                               TABLE OF CONTENTS


Item
----

1.   Press Release entitled "Tele Sudeste Celular Participacoes S.A. - Minutes
     of the Ordinary and Extraordinary General Shareholders' Meetings" dated
     March 27, 2003.




                                                          [GRAPHIC REMOVED HERE]

Tele SUDeste Celular Participacoes S.A.
Minutes of the Ordinary and Extraordinary General Shareholders' Meetings
================================================================================

March 27, 2003   (06 pages)

For more information, please contact:

Charles E. Allen
TELE SUDESTE CELULAR PARTICIPACOES S.A., Brazil
Tel.:    (55-11) 3549-7200
Fax:     (55-11) 3549-7202
E-mail:  callen@telesp.com.br
URL:     www.telefonica.com.br

(Sao Paulo - Brazil), (March 27, 2003) TELE SUDESTE CELULAR PARTICIPACOES S.A.
(NYSE: TSD; BOVESPA: TSEP) hereby informs the Minutes of the 4th Ordinary and
14th Extraordinary General Shareholders' Meeting held on March 25, 2003:

1. Date, Time and Venue of the Meeting: March 25, 2003, at 13:00 hours, at Praia
de Botafogo N(0) 501, 5th Floor - Auditorium, Botafogo, in the Capital of the
State of Rio de Janeiro.

2. Call Notice: The meeting was called upon publication of notice in the
newspapers Official Gazette of the State of Rio de Janeiro, issues of February
19, 20 and 21, 2003 (pages 6, 8 and 5, respectively), Jornal do Comercio, issues
of February 19, 20 and 21, 2003 (pages A-6, A-12 and A-10, respectively) and
Gazeta Mercantil, issues of February 19-20 and 21, 22 and 23, 2003 (pages A-9,
B-3 and B-3, respectively).

3. Agenda:

For the Ordinary General Shareholders' Meeting:
1)   Assess the accounts of the Management, analyze, discuss and vote for the
     approval of the financial statements of the Company, for the fiscal year
     ended December 31, 2002;
2)   Deliberation about the allocation of the results of the operations of the
     fiscal year and distribution of dividends;
3)   Approval of the budget of the Company for 2003;
4)   Election of the members of the Board of Directors
5)   Election of the members of the Audit Committee; and
6)   Definition of the global annual remuneration of the members of the Board of
     Directors and the individual remuneration of the Audit Committee.

For the Extraordinary General Shareholders' Meeting:
1)   Incorporation of a new management system in the Company, thus modifying the
     number of members of the Board of Directors, to a minimum of 3 and a
     maximum of up to 12, their functions and the positions and functions of the
     management. As a result, articles 14, 15, 16, 17, 18, 20, 22 and 23 of the
     Company's by-laws are modified;
2)   Modification of the Company's by-laws to certain dispositions of Law #
     10303/01 regarding the issuance of new shares, thus modifying articles 4
     and 5;
3)   Approval of the wording of article 5 of the Company's by-laws suggested by
     the Board of Directors on its meeting held on April 29, 2002, when it was
     approved a capital increase for the Company, as a result of the
     capitalization of the credit of the majority shareholder resulting from the
     fiscal gains dated from previous fiscal years applied in the subsidiaries
     Telerj Celular S.A. and Telest Celular S.A.; and



4)   Approval of the full modification of the Company's by-laws, aiming its
     modernization and adaptation to the new management system of the Company,
     and execute the consolidation of the Company's by-laws following the
     previous resolutions.

4. Attendants: the shareholders of the Company representing more than 2/3 (two
thirds) of its voting capital, in conformity with the records and signatures in
the Shareholders Attendance Register were present. Were also present the Manager
of the Company, Mr. Eduardo Navarro de Carvalho - Vice-President for Corporate
and Regulatory Planning, the representative of the independent auditors
(Deloitte Touche Tohmatsu), Mr. Alessandro Prado, the representatives of the
Audit Committee, Mr. Wolney Querino Schuler Carvalho and Mr. Flavio Stamm; and
the Company's accountant Mr. Jose Alberto Lopez Lopez.

5. Presiding Officers: Mr. Evandro Luis Pippi Kruel - Chairman and Mrs. Simone
Wilches Braga - Secretary.

6. RESOLUTIONS:

6.1 - Starting the meeting, the Chairman explained that the minutes of the
meeting would be drawn up as a summary of occurred facts, only containing the
transcription of the resolutions, as allowed in article 130, paragraph 1 of the
Corporate Law. He also informed that documents or proposals, voting statements
or withdraws about the subjects to be deliberated should be presented in written
form to the presiding officers, represented by the Secretary of the Meeting for
this purpose. Therefore, regarding the item "1" of the Agenda, it was informed
that the documentation referring to the rendering of accounts by the management
was at the disposal of the shareholders, including the Annual Report, the
Financial Statements, duly accompanied by the Report of Independent Auditors and
the Report of the Audit Committee, all referring to the fiscal year ended
December 31, 2002. Following suit, it was proposed to waive the reading of said
documents, duly accepted, once the present shareholders were fully cognizant of
the contents, which had been fully published in the Official Gazette of the
State of Rio de Janeiro (pages 3 to 8), in "Jornal do Comercio" (page A-8 to
A-10) and "Gazeta Mercantil" (page A-18 to A-20) on February 18, 2003 with
amendment published in the Official Gazette of the State of Rio de Janeiro (page
2), in "Jornal do Comercio" (page A-6) and "Gazeta Mercantil" (page B-2) on
February 20, 2003. The topic of item 1 of the Agenda was presented for
discussion and subsequent voting and was unanimously approved by the
shareholders. It was also requested to be included in the record, the favorable
voting of the minority shareholder Mr. Jose Teixeira de Oliveira. The Annual
Report and the Financial Statements duly accompanied by the Report of the
Independent Auditors and the Report of the Audit Committee (all referring to the
fiscal year ended December 31, 2002) were approved by the present shareholders,
without any restriction or reserve.

6.2 - The item 2 of the Agenda concerning the allocation of the results of the
operations and the distribution of dividends, considering that the pertaining
documents were put at the disposal of the Shareholders and, after reading the
contents, the President of the Meeting submitted the matter for discussion and
voting. The Proposed Allocation of the Results of Operations and Distribution of
Dividends for 2002 was fully approved by unanimous voting of the present
shareholders, registering the favorable vote of the minority shareholder Mr.
Jose Teixeira de Oliveira, without any restriction or reserve. As a consequence
of said approval, the Net Income for the Year, amounting to R$143,615,582.26
(one hundred forty three million, six hundred fifteen thousand, five hundred
eighty two reais and twenty six cents) was accounted for in the "Retained
Earnings" account and shall be expressly allocated as follows: 1- Legal Reserve:
In accordance with the article 193 of Law # 6404/76, 5% (five percent) of net
income shall be allocated to set up a legal reserve of R$7,180,779.11 (seven
million, one hundred eighty thousand, seven hundred seventy nine reais and
eleven cents). 2 -Interest on Company's Net Worth: In accordance with the terms
of article 7 combined with articles 26, 27, and 28 of the Company's By-laws,
article 202, items I, II and III of the Law # 6404/76, article 2



of the Law # 10303/2001 and the Law # 8920/94, the management proposed that the
dividends and the interest on Company's net worth shall be paid to the bearers
of preferred and common shares, as follows:

      Interest on Own Capital - Gross Value                      13,500,000.00
       Withholding Income Tax:                                   (2,025,000.00)
                                                                --------------
      Interest on Capital's Net Worth - Net Value

      Advanced Dividends                                         11,475,000.00
      Complementary Dividends                                    84,370,000.00
                                                                  6,009,319.16
                                                                --------------
      Total Dividends/IONW                                      101,854,319.16
        Common Shares                                            35,751,808.43
        Preferred Shares                                         66,102,510.73

      Dividends/IONW per each lot of thousand shares (Reais)

      Common Shares                                               0.231506
       Preferred Shares                                           0.254657

The payment of the Interest on Company's Net Worth and Complementary Dividends
will be made until December 22, 2003. 3- Retained Earnings: It was approved that
the remaining balance of Adjusted Net Income, on the terms of article 202 of Law
# 6404/76, amounting to R$32,555,483.99 (thirty two million, five hundred fifty
five thousand, four hundred eighty three reais and ninety nine cents), shall be
transferred to the Special Reserve for Expansion and Modernization, because it
is originated in the controlled companies, and will be used in the modernization
and/or expansion of the telecommunications systems, according to the proposed
budgets of the controlled companies.

The Capital Stock of the Company at the end of the fiscal year was
R$685,321,135.81 (six hundred eighty five million, three hundred twenty one
thousand, one hundred thirty five reais and eighty one cents), divided in
154,431,420,977 common shares and 259,575,036,202 preferred shares, totaling
414,006,457,179 shares, all at par value.

6.3 - The item "3" of the Agenda, abiding by the provisions of article 196 of
the Corporate Law, was submitted and unanimously approved by the shareholders,
registering the favorable vote of the minority shareholder Mr. Jose Teixeira de
Oliveira. The consolidated budget amounts to R$225,000,000.00 (two hundred
twenty five million reais), included in the following budget: a) the remaining
balance of the Adjusted Net Income, on the terms of article 202 of the Law #
6404/76, for an amount of R$36,742,273.88 (thirty six million, seven hundred
forty two thousand, two hundred seventy three reais and eighty eight cents); and
b) the funds generated by operations: R$188,257,726.12 (one hundred eighty eight
million, two hundred fifty seven thousand, seven hundred twenty six reais and
twelve cents).

6.4 - On the item "4" of the Agenda, about the election of the members of the
Board of Directors, the President suggested to postpone the voting until the
closing of the Extraordinary General Shareholders' Meeting, since there was a
proposal to modify the number of members of the Board of Directors. The request
was accepted and will be discussed further on in this document.

6.5 - The item "5" of the Agenda, about the election of the members of the Audit
Committee, after the indications duly received by the Presiding Officers and
counting of votes, the following were elected members of the Audit Committee of
the Company: a) by the bearers of the preferred shares representing 3.813% of
the non-voting shares, shareholders represented



by Mrs. Catarina Iazzet Ferreira, in a separate voting with the abstention of
the Majority shareholder, as an effective member: Mr. Flavio Stamm, Brazilian,
married, business administrator, bearer of identity card RG # 12.317.859,
SSP-SP, enrolled in the Individual Taxpayers' Register under CPF #
048.241.708-00, resident in the Capital of the State of Sao Paulo, with
commercial address at Rua Patapio Silva 223, Ap. 32, CEP 05436-010, Sao Paulo,
SP, and as a deputy member Mr. Luciano Carvalho Ventura, Brazilian, married,
economist and business administrator, bearer of identity card RG # 8.147.870
SSP/SP, enrolled in the Individual Taxpayers' Register under CPF #
018.153.854-72, resident in the Capital of the State of Sao Paulo, with
residential address at Rua Marechal Bittencourt 408, Jardim Paulista; b)
following the procedures established by the Law and the Company's by-laws
regarding the election, in separate voting, of the representatives of minority
shareholders to form the Audit Committee, it was verified in the Book of
Showings that the stake of minority shareholders did not reach the required
minimum of 10% of the shares with voting rights, according to the item "a", of
paragraph 4, of article 161 of the Law # 6404/76; c) by the general vote of the
common shares were elected as effective members: Mr. Milton Shigueo Takarada,
Brazilian, married, accountant, bearer of identity card # 12.721.407-0 SSP/SP,
enrolled in the Individual Taxpayers' Register under CPF # 011.319.328-97,
resident in the city of Sao Paulo, State of Sao Paulo, with commercial address
at Rua do Livramento, 66, block A, 1st floor; and Mr. Joao Luis Tenreiro
Barroso, Brazilian, single, economist, bearer of identity card RG #
04.291.751-8, enrolled in the Individual Taxpayers' Register under CPF #
506.464.277-68, resident in the capital of the State of Rio de Janeiro, with
residential address at Rua Humberto de Campos 664, Ap. 501, Leblon, and
commercial address in the Capital of the State of Sao Paulo, at Av. Brigadeiro
Faria Lima 2277, 15th Floor, 1503, Jardim Paulistano; and as deputy members: Mr.
Jose Ricardo de Souza Porpino, Brazilian, married, accountant, bearer of
identity card # 007999/0-3 CRC/PA, enrolled in the Individual Taxpayers'
Register under CPF # 086.622.822-53, with commercial address at Rua Martiniano
de Carvalho 851, 17th Floor, Sao Paulo - SP; and Mr. Jose Guilherme Feijao
Queiroz de Ataide, Portuguese, single, graduated at Law, bearer of identity card
RNE # V355.773-S, enrolled in the Individual Taxpayers' Register under CPF/MF #
224.291.638-61, resident at Rua Melo Alves 751, Ap. 21, Jardim America, Sao
Paulo-SP, with commercial address at Av. Brigadeiro Faria Lima 2277, 15th Floor,
1503, Jardim Paulistano, Sao Paulo - SP. All the Audit Committee Members now
elected shall have the term of office beginning on the present date and expiring
on the date of the Ordinary General Shareholders' Meeting of 2004. It was also
recorded that none of those elected where legally impaired to take office.

6.6 - The item "6" of the Agenda, concerning the definition of the remuneration
of the members of Board of Directors and the Audit Committee, it was unanimously
approved that the annual global remuneration of the Directors shall be fixed in
R$1,100,400.00 (one million, one hundred thousand, four hundred reais), being
the Board of Directors' duty to distribute it among the members and the
Management. It was also unanimously approved that the remuneration of the
members of the Audit Committee shall be fixed in R$2,125.00 (two thousand one
hundred twenty five reais), not computing in this calculation benefits,
allowances and occasional profit sharing (variable compensation), on the terms
of the disposition of the Law # 6404/76. It was registered the favorable vote of
the minority shareholder Mr. Jose Teixeira de Oliveira.

6.7 - Discussion of the agenda of the Extraordinary General Shareholders'
Meeting. The item "1" of the Agenda, was submitted and unanimously approved by
the shareholders, registering the favorable vote of the minority shareholder Mr.
Jose Teixeira de Oliveira, the new administrative system of the Company, thus
modifying the number of members of the Board of Directors, to a minimum of 3 and
a maximum of up to 12, their functions and the positions and functions of the
management. As a result, articles 14, 15, 16, 17, 18, 20, 22 and 23 of the
Company's by-laws are modified, enabling the transcription of such modifications
in the minutes.



6.8 - The item "2" of the Agenda of the Extraordinary General Shareholders'
Meeting was unanimously approved by the majority of the shareholders,
registering the favorable vote of the minority shareholder Mr. Jose Teixeira de
Oliveira, on the modification of the Company's by-laws in order to adapt them to
certain dispositions of Law # 10303/01 regarding the issuance of new shares,
thus modifying the articles 4 and 5 of the Company's by-laws, enabling the
transcription of such modifications in the minutes.

6.9 - The item "3" of the Agenda of the Extraordinary General Shareholders'
Meeting was unanimously approved by the majority of the shareholders,
registering the favorable vote of the minority shareholder Mr. Jose Teixeira de
Oliveira, on the approval of the wording of article 5 of the Company's by-laws
suggested by the Board of Directors on its meeting held on April 29, 2002, when
it was approved a capital increase for the Company, as a result of the
capitalization of the credit of the majority shareholder resulting from the
fiscal gains dated from previous fiscal years applied in the subsidiaries Telerj
Celular S.A. and Telest Celular S.A., enabling the transcription of such
modifications in the minutes.

6.10 - The item "4" of the Agenda of the Extraordinary General Shareholders'
Meeting regarding the full modification of the Company's by-laws, aiming its
modernization and adaptation to the new management system of the Company, the
President clarified that the consolidated by-laws, duly signed by the Presiding
Officers, will be filed in the Company's headquarters, as Doc. 1, and will have
a copy filed in relevant Junta Comercial (Business Board). Being the Company's
consolidated by-laws already at the disposition of the shareholders and after
reading the contents, the President submitted the topic to discussion and
voting, being fully and unanimously approved by the shareholders, without any
restriction or observation, registering the favorable vote of the minority
shareholder Mr. Jose Teixeira de Oliveira.

6.11 - Once approved the reform and consolidation of the Company's by-laws, the
shareholders returned to the item "4" of the Agenda of the Ordinary General
Shareholders' Meeting regarding the election of the members of the Board of
Directors. The President of the Meeting clarified that, in accordance to the
Call Notice for the Meeting, the minimum percentage of the capital stock to
participate in the multiple voting for the members of the Board of Directors was
5% (five per cent) of the voting capital and none of the shareholders filed the
request with the minimum preceding time established by Law, 48 hours. The
following were unanimously reelected to be part of the Board of Directors,
registering the favorable vote of the minority shareholder Mr. Jose Teixeira de
Oliveira: Mr. Felix Pablo Ivorra Cano, Spanish, married, engineer, bearer of
identity card RNE V250982-E, enrolled in the Individual Taxpayers' Register
under CPF 055.076.307-47, resident in the capital of the State of Rio de
Janeiro, with commercial address at Praia de Botafogo 501, 8th Floor, Torre
Corcovado, Botafogo, Rio de Janeiro - RJ; Mr. Fernando Xavier Ferreira,
Brazilian, married, engineer, bearer of identity card 585.363 SSP/PR, enrolled
in the Individual Taxpayers' Register under CPF 142.144.239-68, resident in the
capital of the State of Sao Paulo, with commercial address at Rua Martiniano de
Carvalho 851, 21st Floor, Sao Paulo - SP; Mr. Antonio Pedro de Carvalho
Viana-Baptista, also signing as Antonio Viana-Baptista, Portuguese, married,
economist, bearer of passport No. R-026509, valid until April 02, 2011, enrolled
in the Individual Taxpayers' Register under CPF 222.541.978-78, resident in the
city of Madrid, Spain, with commercial address at Paseo de Recoletos 7-9, 3rd
Floor; Mr. Ernesto Lopez Mozo, Spanish, married, economist, bearer of passport
No. 513 736 39-B, valid until September 12, 2005, resident in Spain, with
commercial address at Paseo de Recoletos 7-9, Madrid, Spain; and Mr. Kazuo
Moriya, Japanese, married, business administrator, bearer of identity card RNE #
V100063-H SE/DPMAF/DPF, enrolled in the Individual Taxpayers' Register under CPF
# 023.673.037-11, resident in the capital of the State of Rio de Janeiro, at Rua
Sambaiba 68, Ap. 602, Leblon. The following were elected: Mr. Zeinal Abedin



Mohamed Bava, Portuguese, married, engineer, bearer of Portuguese passport No. G
312.206, valid until February 27, 2012, enrolled in the Individual Taxpayers'
Register under CPF/MF 057.368.807-92, resident in Portugal, at Rua Fernando
Namora 34, Ap. 9, Lisboa; Mr. Carlos Manuel de Lucena e Vasconcelos Cruz,
Portuguese, married, business manager, bearer of Portuguese passport No. E
197.204, valid until July 19, 2003, enrolled in the Individual Taxpayers'
Register under CPF/MF 227.739.558-70, resident in Portugal, at Quinta Patino,
Av. da Republica 1910, Lot 12, Alcoitao; Mr. Iriarte Jose de Araujo Esteves,
Portuguese, married, engineer, bearer of Portuguese passport No. F 370.234,
valid until February 02, 2010, resident in Portugal, at Rua Carlos Anjos 21,
R/Chao, Estoril, concelho de Cascais; Mr. Eduardo Perestrelo Correia de Matos,
Portuguese, married, economist, bearer of identity card RG 35.939.115-1 SSP/SP,
enrolled in the Individual Taxpayers' Register under CPF/MF 186.001.968-41,
resident in the city of Sao Paulo, State of Sao Paulo, with residential address
at Rua Breno Pinheiro 262, Morumbi, CEP 05661-000, and commercial address at Av.
Brigadeiro Faria Lima 2277, 15th Floor, 1503, Jardim Paulistano, CEP 01452-000;
Mr. Paulo Jorge da Costa Goncalves Fernandes, Portuguese, married, engineer,
bearer of Portuguese passport No. G 196.267, valid until August 07, 2011,
resident in Portugal, at Rua Neutel de Abreu 13, 12-B, Benfica, Lisboa; and Mr.
Ignacio Aller Mallo, Spanish, married, business manager, bearer of Spanish
passport No. Q 666192, valid until March 03, 2013, resident in Spain, at Calle
Goya 24, Madrid. The Directors now elected will have their mandate expiring 3
(three) years from this date. It is also registered that the controller
shareholder Sudestecel Participacoes S.A., that appointed the Directors,
obtained from the recently elected Directors the information that they are in
condition to sign the declaration mandated by CVM Instruction # 367/2002 and
that they committed themselves to file such signed declaration at the moment of
taking their office. The start of the mandate for Directors resident abroad is
conditioned to the appointment of a representative resident within the country.

7. Closing of the Meeting: At the end of the meeting as there were no more
subjects to be discussed, this minute was approved and signed by the
shareholders and will henceforth be contained in the meeting log. It is
registered statement of the minority shareholder Mr. Jose Teixiera de Oliveira
in favor of the job done by Mr. Paulo Cesar Pereira Teixeira, Executive Vice
President of Operations of the controlled companies, Telerj Celular S.A. and
Telest Celular S.A. It is also registered the statement of the minority
shareholder, Mr. Gilberto Souza Esmeraldo, in favor of the job done by the
General Secretary and the Legal Department. In accordance to the paragraph 2 of
article 130, of the Law # 6404/76, the publication of the minutes without
including the signatures of the shareholders is authorized. Rio de Janeiro,
March 25, 2003.

Signatures:
Evandro Luis Pippi Kruel - President
Simone Wilches Braga - Secretary
Sudestecel Participacoes S.A. - represented by Mr. Evandro Luis Pippi Kruel
Brasilcel B.V. - represented by Mrs. Evandro Luis Pippi Kruel
Tagilo Participacoes Ltda. - represented by Mrs. Simone Wilches Braga

Represented by Mrs. Catarina Iazzet Ferreira
Credit Suisse First Boston Garantia "Proprio" Fundo Mutuo de Investimento
em Acoes
Credit Suisse First Boston Equity Investments (Netherlands) B V
Brasil Fixed Income Equity Investments (Netherlands) B V
Banco de Investimentos Credit Suisse First Boston S.A

Mr. Jose Teixeira de Oliveira

Mr. Gilberto Souza Esmeraldo




                                    SIGNATURE

     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.

                                    TELE SUDESTE CELLULAR HOLDING COMPANY

Date:      March 27, 2003.          By:   /s/  Charles E. Allen
                                          ---------------------------
                                          Name:    Charles E. Allen
                                          Title:   Investor Relations Director