---




SECURITIES AND EXCHANGE COMMISSION


Washington, D.C. 20549





---




FORM 6-K





Report of Foreign Private IssuerPursuant to Rule 13a-16 or 15d-16 of the


Securities Exchange Act of 1934





For the month of June 2004
  Commission File Number 001-14495





---






TELE NORDESTE CELULAR PARTICIPAÇÕES S.A.


(Exact name of registrant
as specified in its charter)









Tele Nordeste Cellular Holding Company


(Translation of Registrant's name into English)







Av. Ayrton Senna da Silva, 1633 - 2° andar 
  54410-240 Jaboatão dos Guararapes
  Pernambuco
  Federative Republic of Brazil


(Address of principal executive office)







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

(Check One) 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)) (Check One) 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) (Check One) Yes _____ No  X ( Indicate by check mark
whether the registrant by furnishing the information contained in this Form 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


---





| | Filer: Tele
      Celular Sul Participações S.A. 
      Proposed merger with Tele Nordeste Celular Participações S.A.
      Registration No. 333-116330
| | -------------------------------------------------------------------------------------------------------------------------------------------------------





| | Tele Celular
      Sul Participações S.A.
      Tele Nordeste Celular Participações S.A.
| | ----------------------------------------------------------------------------------------



June 2004

| | In connection
      with this proposed transaction, Tele Celular Participações
      S.A. (TSU) has filed relevant materials with the SEC, including TSU's registration
      statement containing a preliminary prospectus, which was filed on June 09,
      2004. The definitive prospectus will be sent to holders of Tele Nordeste
      Celular Participações S.A.'s (TND) preferred shares and ADRs
      when it becomes available. INVESTORS AND SECURITY HOLDERS ARE URGED TO READ
      THE PRELIMINARY PROSPECTUS ON FILE WITH THE SEC, THE DEFINITIVE PROSPECTUS
      WHEN IT BECOMES AVAILABLE, AND ANY OTHER RELEVANT DOCUMENTS FILED BY TSU
      OR TND, BECAUSE THEY CONTAIN, OR WILL CONTAIN, IMPORTANT INFORMATION. Investors
      and security holders may obtain a free copy of the preliminary prospectus
      and the definitive prospectus (when it becomes available) and other documents
      filed by TSU and TND with the SEC for free at the SEC's web site at www.sec.gov.
      The preliminary prospectus and the definitive prospectus (when it becomes
      available), and the other documents filed by TSU, may also be obtained free
      from TND by calling +55 81 3302-2594. | 
| | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | 



Agenda


---

I. Description
of the Proposed Merger Transaction of TND and TSU

II.        Strategic
Overview of Tele Celular Sul

III.        Strategic
Overview of Tele Nordeste Celular

IV. Overview
  of the "New Company "



Agenda


---

I. Description
of the Proposed Merger Transaction of TND and TSU

II.        Strategic
Overview of Tele Celular Sul

III.        Strategic
Overview of Tele Nordeste Celular

IV. Overview
  of the "New Company"



Current Ownership
Structure  TSU and TND

|Ownership Structure - TSU | Ownership Structure - TND
|------------------------- | -------------------------
|                          |                          
|                          |                          



Merger of TND and TSU

|Proposed Merger | Pro-Forma Structure Post Merger
|--------------- | -------------------------------
|                |                                
|                |                                



Overview of the
Transaction

- The
proposed transaction contemplates the merger of TND into TSU

- TSU will be
the surviving entity

- TND will be
the incorporated entity

- The merger
is being done at the holding companies level, therefore there will be no direct impact to
the operating companies        TIM Sul e TIM Nordeste

| | Tax
benefits given to Tim Nordeste will remain the same
| | -------------------------------------------------------

- As a result
of the merger, both companies TIM Nordeste and TIM Sul will be controlled by the new
entity



Overview of the
Transaction  Cont.

- Shareholders
of TND will receive the same class of shares of TSU:

| | TND
ON shareholders will receive 0.9261 TSU ON shares for each TND ON share
| | ---------------------------------------------------------------------------

| | TND
PN shareholders will receive 0.9261 TSU PN shares for each TND ON share
| | ---------------------------------------------------------------------------

| | TND
ADS holders will receive 1.8522 of TSU ADS for each TND ADS that they hold
| | ------------------------------------------------------------------------------

- Dissident
shareholders who own voting shares of TND will have withdrawal rights

- Shareholders
who own non-voting shares of TND will not have withdrawal rights

| | TND
preferred shares fulfill liquidity and dispersion legal requirements, and therefore do
not have withdraw rights
| | -------------------------------------------------------------------------------------------------------------------

- Shareholders
of TSU do not have withdrawal rights

| | Brazilian
Law establishes that shareholders of the surviving entity are not granted withdrawal
rights in merger of entities
| | ---------------------------------------------------------------------------------------------------------------------------



Key Objectives of the
Transaction

- Concentration
of the liquidity of the shares of both companies TND and TSU

| | We
expect the new entity to be one of the three largest wireless companies in Brazil in
terms of market cap
| | -----------------------------------------------------------------------------------------------------------

- Reduction
of operating and administrative costs

| | Eliminate
one of the two corporate structures
| | ---------------------------------------------

| | Systems
integration
| | -------------------

| | Expected
to compensate, at the very least, all costs associated with executing the merger
| | -----------------------------------------------------------------------------------------



Market
Capitalization (In R$ millions)

Current Scenario:

|Scenario Post-Transaction:
|--------------------------

| | Number
of shares based on 1Q/2004 companies financials and share price as of the previous day to
the transaction announcement (05/31/2004)
| | ------------------------------------------------------------------------------------------------------------------------------------------



Assumptions Related to
the Proposed Exchange Ratio

- ABN AMRO
Real was jointly selected by TSU and TND to render an independent valuation of both
companies TSU and TND base on        the economic value criteria

- The
companies were valued as stand alone operations

- The
valuation methodology used was discounted cash flow analysis

| | The
base date assumed was March 31, 2004
| | ----------------------------------------

| | Based
on 10-year projections (2004-2013)
| | ----------------------------------------

- Range of
discount rates (WACC):

| | From
16.1% to 18.1% in nominal Reais
| | ------------------------------------

- Range of
perpetuity growth rates:

| | From
4.18% to 5.18% in nominal Reais
| | ------------------------------------



Results of the Valuation

- The equity value range
for TSU goes from R$ 2.4 billions to R$ 2.9 billions. The mid-point of the value range
implies:
EV/EBITDA (2004)
multiple of 6.3x
- EV/EBITDA (2004)
multiple of 6.3x
- The equity value range
for TSU goes from R$ 2.2 billions to R$ 2.7 billions. The mid-point of the value range
implies:

EV/EBITDA (2004)
multiple of 6.2x
- EV/EBITDA (2004)
multiple of 6.2x
- Based on these equity
value ranges for TSU and TND, the exchange ratio between TSU and TND shares would be
comprised in the        range of 0.9215 TSU shares for each TND share to 0.9300 TSU
shares for each TND share



Proposed Exchange Ratio
 Comparison with Market Expectations

| | Considers
average exchange ratio for the indicated period based on market capitalization until the
previous day to the Board Meeting (28/05/2004)
| | -------------------------------------------------------------------------------------------------------------------------------------------------



Next Steps

In the next weeks, TND
and TSU will be fulfilling legal requirements of Brazilian and U.S. Law in order to
conclude the transaction.

- Filling of
the F-4 form (describing the transation) with the SEC

- Preparation
of audited financial statements as of June 30, 2004

| | To
serve as a basis for appraisal of (i) book value and (ii) book value adjusted to market.
These appraisals will serve as                basis to the determination of the value of
the right to withdrawal and will be prepared by the independent appraiser
               Acal
| | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

- Meeting of
the Boards of Directors of TND and TSU to authorize the signature of the final version of
the protocol and        justification of merger expected to happen in July



Next Steps  Cont.

- Publication
of Material Fact Notice including the final terms of the merger

| | Value
of withdrawal rights, increase in TSUs capital stock, etc.
| | ----------------------------------------------------------------

- Publication
of the summons notices for the Special Shareholders Meetings of TND and TSU, which shall
decide on the merger

- Declaration
of effectiveness of Form F-4 issued by SEC

- Decision of
Special Shareholders Meetings of TND and TSU on the merger and publication of the minutes

| | 30
day-term for exercising withdrawal rights by the common shareholders of TND
| | ------------------------------------------------------------------------------

- Closing of
the transaction

| | Expected
to the second semester of 2004
| | ---------------------------------------



Agenda


---

I. Description
of the Proposed Merger Transaction of TND and TSU

II. Strategic
Overview of Tele Celular Sul

III.        Strategic
Overview of Tele Nordeste Celular

IV. Overview
  of the "New Company"



Tele Celular Sul (TSU)
Region

| | Area: Paran, Santa
Catarina and Pelotas regionPopulation: 15.4
millionsPopulation Covered:

TDMA
                - 82%GSM -   61%Total Penetration: 27%Subscribers: 2.2
millionsTechnology: TDMA and
GSMMarket Share: 53%Competitors: Vivo
(Telefnica and Portugal Telecom), Claro (Telecom Amricas Group) and Brasil Telecom
| | -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------



Main Achievements in
the First Quarter of 2004

- Expansion
      of GSM coverage - 61% of the population

- Successful
PCS migration

- 365%
increase in net additions: GSM is the driver

- 142% growth
in VAS revenues

- 33%
increase in gross revenue

- 11%
decrease in subscriber acquisition cost (SAC)

- 10% increase
      in profitability - EBITDA of R$ 108.1 million

- R$ 32.4
      million net income - 13% increase compared to 1Q03

- Low
indebtedness



Increase in Sales with
Cost Reduction

|Gross AdditionsThousands | Subscriber Acquisition Cost (SAC)
R$
|------------------------ | ------------------------------------
|                         |                                     
|                         |                                     



Strong Growth in
Subscriber Base

|Net Additions
Thousands | Subscribers

Thousands
|----------------------- | ----------------------
|                        |                       
|                        |                       



Strong Performance of
ARPU

Total ARPU R$



Gross Revenue Growth

|Gross RevenueR$ Millions | 
|------------------------ | 

|                               |         |  | 1Q04     |  | Variation
|------------------------------ | ------- |  | -------- |  | ---------
|                              
|Handsets Revenue (R$ millions) | 77.1    |  | + 169.5%
|Handsets sold (thousands)      | 251.2   |  | + 265.1%
|                              
|Service Revenue (R$ millions)  | 344.7   |  | + 19.3% 
|Subscribers (thousands)        | 2,192.1 |  | + 25.0% 
|Average increase in tariffs    | 8.1%    |  | + 8.1%  
|VAS (R$ millions)              | 15.5    |  | + 142.2%



EBITDA Performance

EBITDA margin reflects
the strong subscriber gross addition in the period

EBITDA R$ Millions



Low Debt, High Liquidity

|Total Debt
                                                              R$ Millions | Net Cash

                                                              R$ Millions
|------------------------------------------------------------------------------------ | -----------------------------------------------------------------------------------
|                                                                                     |                                                                                    
|                                                                                     |                                                                                    



Increase in
Profitability

Net IncomeR$ Millions



Strategies for 2004

- Focus on
continued growth in subscriber base

- Retention
programs: Value & Volume

- Expansion
of GSM coverage

- Continue
innovating

- Integrations
and Synergy: Plug & Play, national coverage, commercial synergy



Agenda


---

I. Description
of the Proposed Merger Transaction of TND and TSU

II.        Strategic
Overview of Tele Celular Sul

III. Strategic
Overview of Tele Nordeste Celular

IV. Overview
  of the "New Company"



Tele Nordeste Celular
(TND) Region

| | Area: Alagoas,
Pernambuco, Paraba, Rio Grande do Norte, Cear and PiauPopulation: 27.2
millionsPopulation Covered
(March/04):

TDMA - 75%GSM -   48%Total Penetration: 17%Subscribers: 2.3
millionsTechnology: TDMA and
GSMMarket Share: 47%Competitors: Oi
(Telemar S.A) and Claro (Telecom Amricas Group)
| | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------



Main Achievements in
the First Quarter of 2004

- Fast
expansion of the GSM coverage  48% of the population

- Merger of
the 6 operators into Tim Nordeste

- 46% growth
in gross additions over the 1Q/03

- 75.8%
 increase in net additions and 14.4% increase in subscriber base compared to 1Q/2003

- R$108
millions EBITDA

- Low
indebtedness

- R$ 47.0
millions net income  42.4% increase compared to 2003



Increase in Sales

|Gross Additions
                                                              Thousands | Subscriber Acquisition Cost (SAC)

                                                              R$
|--------------------------------------------------------------------------------------- | ---------------------------------------------------------------------------------------------------
|                                                                                        |                                                                                                    
|                                                                                        |                                                                                                    



ARPU

|Subscriber Base (postpaid) | Total ARPUR$                                   
|-------------------------- | -----------------------------------------------
|                           |                                                
|                           |                                                
|Subscriber Base (prepaid)  | Rule 45/55Growth of
the prepaid subscriber base
|                           |                                                
|                          



Strong Growth of the
Subscriber Base

|Subscribers

                                                              Thousands | Net Additions

                                                              Thousands
|------------------------------------------------------------------------------------ | --------------------------------------------------------------------------------------
|                                                                                     |                                                                                       
|                                                                                     |                                                                                       



Gross Revenue Growth

Service revenue growth

Gross Revenue
                                                              R$ Millions



EBITDA Performance

EBITDA
                                                              R$ Millions



Low Debt, High Liquidity

|Total Debt
                                                              R$ Millions | Net Cash

                                                              R$ Millions
|------------------------------------------------------------------------------------ | -----------------------------------------------------------------------------------
|                                                                                     |                                                                                    
|                                                                                     |                                                                                    



Increase in Net Income

Strong performance

Net Income R$ Millions



Strategies for 2004

|Retain and maintain loyalty of the subscriber base
|--------------------------------------------------

+

|Incentivize
  consumption / increase in revenue per user
|--------------------------------------------------------

+

|Qualified
  growth of the base
|------------------------------

=

|Growth with Profitability
|-------------------------



Strategies for 2004

| | Absolute leader in the regionBest cellular service (Innovation e Quality)High performance company (Operational and Financial)Productive work environment where people feel proud and satisfactionIntegrated and productive relationship with partners
| | -----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------



Agenda


---

I. Description
of the Proposed Merger Transaction of TND and TSU

II.        Strategic
Overview of Tele Celular Sul

III.        Strategic
Overview of Tele Nordeste Celular

IV.
  Overview of the "New Company"



Preliminary Overview
of the New TSU

|        | We expect the new entity to be
     one of the three largest wireless companies in Brazil in terms of market
  cap
|------- | ------------------------------------------------------------------------------------------------------------------
|        |                                                                                                                   
|        | Subscribers


        (000)1                                                                                      
|        |                                                                                                                   
|TSU     | 2,192                                                                                                             
|TND     | 2,263                                                                                                             
|        |                                                                                                                   
|New TSU | 4,455                                                                                                             
|        |                                                                                                                   

|  | 1                                                                                 | As
  of 03/31/2004
|- | --------------------------------------------------------------------------------- | ------------------
|2 | Assumes
  last twelve months for revenue and EBITDA figures                      
|3 | Share
  price as of the previous day to the transaction announcement (05/31/2004)



Additonal
Considerations

Forecasted
Scenarios for TSU

- Expansion
  of GSM coverage

|- | Temporary pressure in marketing expenses
|- | ----------------------------------------
|  |                                         
|- | Temporary increase in network costs     
|  |                                         
|- | Temporary pressure in EBITDA margins    

- Challenging
market    environment

|- | Temporary increase
    in comercialization costs                                                   
|- | ---------------------------------------------------------------------------------------------------
|  |                                                                                                    
|- | Market share reduction
    associated with the entrance of a fourth player (Brasil Telecom) in 2004
|  |                                                                                                    
|- | Temporary pressure
    in EBITDA margins                                                           



Additonal Considerations

Forecasted Scenarios
for TND

- Expansion
of GSM coverage

| | GSM
overlay in its initial stage
| | --------------------------------

| | Temporary
pressure in marketing expenses
| | ----------------------------------------

| | Temporary
increase in network costs
| | -----------------------------------

| | Temporary
pressure in EBITDA margins
| | ------------------------------------

- Tough
market environment

| | Temporary
increase in commercialization costs
| | ---------------------------------------------

| | Market
share reduction associated with the future entrance of a fourth player
| | -----------------------------------------------------------------------------

| | Temporary
pressure in EBITDA margins
| | ------------------------------------



Q & A



CAUTIONARY STATEMENT
CONCERNING FORWARD-LOOKING STATEMENTS

- management
strategy;

- synergies;

- operating
efficiencies;

- integration
of new business units;

- market
position;

- revenue
growth;

- cost
savings;

- capital
expenditures;

- flexibility
in responding to market conditions and the regulatory regime;

- regulatory
action;

- influence
of controlling shareholders;

- litigation;
and

- the
timetable for the merger.

Forward-looking
statements may be identified by words such as "believes," "expects," "anticipates,"
       "projects," "intends," "may, "should," "seeks,"  "estimates," "future,"
"forecast," plan,"        "predict" and "target" or similar expressions.

These statements
reflect our current expectations.  They are subject to a number of risks and
       uncertainties, including but not limited to changes in technology, regulation, the
global cellular        communications marketplace and local economic conditions.  In
light of the many risks and        uncertainties surrounding this marketplace, you should
understand that we cannot assure you that the        forward-looking statements contained
in this presentation will be realized.  You are cautioned not        to put undue
reliance on any forward-looking information.



---

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 NORDESTE CELULAR  PARTICIPAÇÕES, S.A.
|------------------------- | ------------------------------------------
|                         
|Date:
      June 10, 2004 | By:                                       
|                          |                                           
|                          |                                           

---