(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:   ý      Form 40-F:   o 

(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:   o      No:   ý 

(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:   o      No:   ý 

(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:   o      No:   ý 

Oscar Thompson
CEO and Head of Investor Relations
oscar@telepart.com.br
Phone: +55 31 9933-3077
Renata Pantoja
Investor Relations Manager
rpantoja@telepart.com.br
Phone: +55 31 9933-3535

TELEMIG CELULAR PARTICIPAÇÕES S.A.
REPORTS FIRST QUARTER 2007 RESULTS

-   EBITDA of R$121.2 million or 40.4% of net service revenues in the 1Q07
-   Net income of R$42.6 million in the quarter
-   Net additions of 60,378 clients in the quarter
-   Market share in the Triângulo Mineiro region estimated at 18.1%

Brasília, Brazil, May 02, 2007 – Telemig Celular Participações S.A. (BOVESPA: TMCP3 (Common)/TMCP4 (Preferred); NYSE: TMB), the holding company of the wireless telecommunications service provider in the State of Minas Gerais, today announced its first quarter 2007 results. Net additions amounted to 60,378 in the quarter, increasing the Company’s client base to 3,495,940. EBITDA reached R$121.2 million in the 1Q07, representing 40.4% of net service revenues.

Operations Highlights:

The Company’s client base reached 3,495,940 in the first quarter of 2007, representing an increase of 94,630 clients when compared to the same quarter of last year. Net additions amounted to 60,378 in the quarter.

In the 1Q07, prepaid net additions amounted to 79,403, bringing the total prepaid base to 2,716,785, or 78% of the total base. The postpaid base decreased by 19,025 customers, ending the quarter with 779,155, or 22% of the total base.

CLIENT BASE (000s)

www.telemigholding.com.br - 1/13

In the first quarter of the year, blended annualized churn rate decreased by 24.6 percentage points, reaching 29.5% when compared to the 54.1% registered in the previous quarter, as a result of the reduction in both postpaid and prepaid churn rate. When compared to the same quarter of the previous year, blended churn rate decreased by 0.7 percentage points in the quarter, as a consequence of the reduction in the prepaid churn rate.

In the 1Q07, prepaid annualized churn rate decreased by 31.7 percentage points to 31.6% from 63.3% in the 4Q06. When compared to the 1Q06, the prepaid churn rate fell by 1.6 percentage point. It should be noted that the prepaid churn rate reached its lowest level since the second quarter of 2004, before the fourth player started operating in the Company’s authorization area 4.

Annualized churn rate for the postpaid segment, which accounts for most of the revenues generated, decreased by 2.1 percentage points over the 4Q06, reaching 22.1% . Despite the increasingly competitive environment, the Company was able to reduce the postpaid churn rate. When compared to the first quarter of 2006, postpaid churn rate increased by 0.8 percentage point.

CHURN RATE (annualized)

Net service revenues totaled R$299.8 million in the quarter, representing a decrease of R$9.5 million or 3.1% over the previous quarter, primarily resulting from the 3.3% decrease in total traffic (3.2% decrease in incoming and 3.3% decrease in outgoing traffics). This reduction was a consequence of seasonal factors.

When compared to the 1Q06, net service revenues increased by R$49.7 million, or 19.9%, mainly due to the increase of interconnection revenues in the amount of R$36.7 million, or 43.3%, as a consequence of the adoption of the “full billing” rule for interconnection charges. Excluding the “full billing” impacts, net service revenues would have reached R$243.1 million in the 1Q07, R$6.9 million lower than the same quarter of the previous year, basically due to higher volume of free minutes offered to users and lower postpaid client base.

Data revenues totaled R$19.8 million in the 1Q07, representing a slight decrease when compared to the R$22.0 million recorded in the 4Q06 and the 21.0 million registered in the 1Q06, due to the reduction in the postpaid client base and the revision of user packages and promotions.

www.telemigholding.com.br - 2/13

Net equipment revenues for the quarter totaled R$17.0 million, R$14.3 million lower than the R$31.3 million registered in the 4Q06. This decrease was already expected and was associated with lower seasonally-driven sales. When compared to the same period of the previous year, net equipment revenues fell by R$11.3 million in the quarter, due to decreased handset sales.

In the first quarter of the year, handset subsidies for client acquisitions reached R$7.0 million, or R$22.2 per gross addition, compared to R$19.3 million, or R$40.7 per gross addition in the 4Q06, once again due to the period seasonality. When compared to the 1Q06, handset subsidies for client acquisitions decreased by R$3.6 million.

As a result, total net revenues reached R$316.7 million in the 1Q07, 7.0% lower than the previous quarter. When compared to the first quarter of 2006, total net revenues in the 1Q07 increased by R$38.4 million, or 13.8% .

Cost of services totaled R$99.3 million in the first quarter, 3.3% lower than the R$102.6 million registered in the previous quarter, primarily due to lower interconnection expenses resulting from period seasonality. When compared to the 1Q06, cost of services increased by R$38.1 million, or 62.3% in the period, mainly due to the higher interconnection costs caused by the adoption of the “full billing” rule.

Selling and marketing expenses totaled R$45.1 million in the 1Q07, 30.7% lower than the R$65.1 million recorded in the previous quarter, due to the reduction in promotional and advertising expenses, associated with the seasonal reduction of gross additions in the period. When compared to the same period of the previous year, selling and marketing expenses decreased by R$15.3 million due to (i) lower expenses related to promotions and advertising, (ii) lower expenses with dealers’ commissions as a result of the change in the commission rules in the 3Q06, and (iii) the positive impact of the adjustment of inventories to market value.

Customer acquisition cost in the first quarter of 2007 decreased to R$124 from R$129 in the 4Q06, representing the lowest figure since the third quarter of 2004, before the fourth player started operating in the Company’s authorization area 4. When compared to the first quarter of 2006, customer acquisition cost decreased by R$42.

Retention costs reached R$45.7 million in the quarter, higher than the R$42.6 million registered in the 4Q06 due to higher retention discounts and subsidies. When compared to the 1Q06, retention costs in the quarter increased by 18.5% due to the efforts to retain the best and most profitable customers in the base.

General and administrative expenses reached R$20.2 million in the 1Q07, representing a reduction of 40.8% when compared to the R$34.1 million recorded in the previous quarter. It should be noted that G&A expenses in the 4Q06 were negatively affected by higher consulting expenses associated with the entry of the Company’s new management. When compared to the 1Q06, G&A expenses slightly increased by R$0.7 million in the quarter, mainly due to higher managerial consulting expenses.

Bad debt provisions reached R$10.5 million in the 1Q07, slightly higher than the R$9.4 million registered in the previous quarter, due to typical first-quarter seasonality. When compared to the first quarter of 2006, bad debt provisions decreased by 10.7%, due to the establishment of

www.telemigholding.com.br - 3/13

stricter rules governing the client acquisition process, with a focus on credit analysis and strong efforts to recover overdue billings since April 2006. As a percentage of net service revenues, bad debt provisions reached 3.5%, versus 3.0% in the 4Q06 and 4.7% in the 1Q06. When calculated against total net revenues, bad debt provisions totaled 3.3% in the 1Q07.

BAD DEBT PROVISIONS (R$ million)

Postpaid MOU (minutes of use) totaled 187 in the 1Q07, 5.1% down on the 197 minutes posted in the previous quarter, due to period seasonality. When compared to the 1Q06, postpaid MOU in the quarter increased by 6.3% due to higher number of free promotional minutes offered.

Postpaid ARPU reached R$76.8 in the quarter, R$2.9 lower than the R$79.7 registered in the 4Q06, as a consequence of lower traffic per user. When compared to the first quarter of 2006, postpaid ARPU increased by 20.0% in the 1Q07, due to the adoption of the “full billing” rule. Excluding this impact, postpaid ARPU would have reached R$65.6, an increase of R$1.6 when compared to 1Q06, due to higher volume of outgoing and incoming traffic.

In the first quarter of 2007, prepaid MOU reached 34, remaining stable with the last quarter of 2006 and 25.9% higher than the 1Q06, due to increased volume of outgoing minutes.

Prepaid ARPU totaled R$13.2 in the 1Q07, remaining fairly stable when compared to the R$13.5 registered in the previous quarter. When compared to the first quarter of 2006, prepaid ARPU increased by 38.9% in the 1Q07, due to the adoption of the “full billing” rule. Excluding this impact, prepaid ARPU would have reached R$9.4, remaining fairly stable when compared to the R$9.5 registered in the same period of the last year.

As a result, total blended MOU reached 69 minutes in the 1Q07, a decrease of 4.2% over the 4Q06 and an increase of 7.8% over the 1Q06. Blended ARPU totaled R$27.6 in the quarter, R$1.4 lower than R$29.0 registered in the 4Q06 and R$4.3 higher than R$23.3 recorded in the 1Q06.

www.telemigholding.com.br - 4/13

ARPU (R$)

Total market share was estimated at 31.1% in the first quarter of the year, versus 31.6% in the 4Q06. Excluding the Triângulo Mineiro region, market share was estimated at 32.4%, compared to the 33.1% in the previous quarter. For the Triângulo Mineiro region, market share was estimated at 18.1%, higher than the 17.3% registered in the fourth quarter of 2006.

Total gross sales share for the 1Q07 was estimated at 28.7% . Excluding the Triângulo Mineiro region, gross sales share was estimated at 28.6%, versus 30.4% recorded in the 4Q06. For the Triângulo Mineiro region, gross sales share was estimated at 29.6%, versus 29.9% registered in the fourth quarter of 2006.

EBITDA and the EBITDA margin (excluding handset revenues) totaled R$121.2 million and 40.4%, respectively, in the first quarter of 2007, compared to R$78.7 million and 25.5% registered in the previous quarter. When compared to the 1Q06, EBITDA and the EBITDA margin increased by R$34.7 million and 5.8 percentage points, respectively, mainly due to the adoption of the “full billing” rule. Excluding this impact, EBITDA would have reached R$100.1 million in the 1Q07, representing 41.2% of net service revenues.

EBITDA (R$ million)

www.telemigholding.com.br - 5/13

For the 1Q07, depreciation and amortization expenses amounted to R$50.6 million, higher than the R$47.7 million registered in 4Q06 and the R$41.2 million recorded in the first quarter of 2006, reflecting site activations and acceptance.

In the 1Q07 financial statements, the Company reclassified expenses from the amortization of the tax credits associated with the goodwill transferred from the parent company – Telpart Participações S.A. These expenses were transferred from “Depreciation and amortization” to “Income tax and social contribution expenses” in the income statement. For comparative purposes, the same reclassification, in the amount of R$5.4 million per quarter, was applied to the income statements for the quarters of 2006.

DETAILED FINANCIAL INCOME INFORMATION

Net income for the 1Q07 totaled R$42.6 million, or R$2.381 per ADS (R$0.119 per 1,000 shares), 52.0% higher than the 4Q06 and 34.8% higher than the 1Q06.

www.telemigholding.com.br - 6/13

As of March 31, 2007, total debt totaled R$219.4 million, of which R$164.0 million related to long term debt and R$55.4 million related to accounts payable from hedging operations.

On March 31, 2007, 100% of the long term debt (R$164.0 million) was denominated in US Dollars and 100% hedged.

As of March 31, 2007, the Company’s indebtedness was offset by cash and cash equivalents and temporary cash investments in the amount of R$590.5 million, resulting in a negative net debt of R$371.1 million.

NET DEBT (R$ million)

During the first quarter of 2007, Telemig Celular’s capital expenditures reached R$11.5 million. The breakdown of such investments is as follows:

CAPEX BREAKDOWN

www.telemigholding.com.br - 7/13

Free cash flow in the 1Q07 was positive by R$67.9 million, compared to the negative R$153.1 million registered in the previous quarter. The improvement was mainly due to the increase in EBITDA, lower investments and the reclassification of the debt associated with Notes as long term. When compared to the negative free cash flow of R$18.5 million registered in the 1Q06, free cash flow also improved as a result of higher EBITDA and lower hedge expenses, in the 1Q07.

Telemig Celular S.A. and Amazônia Celular S.A. have received express consent (“Consent”) from holders of most of the Notes issued by Telemig and the Notes issued by Amazônia (“Notes”), due in 2009, related to the non-compliance, by Amazônia, with the financial indicators (“covenants”) associated with said Notes.

The non-compliance with these covenants derived from the decision by Amazônia’s management to revise the provisions for contingencies recorded by the Company, pursuant to CVM Resolution 489, referring to lawsuits concerning the illegality of ICMS charges on subscriptions and added-value services.

In addition, financial covenants were changed from “maintenance” to “incurrence”, which will ensure the Company greater financial flexibility.

Due to above mentioned Consent, Telemig and Amazônia will pay an additional US$ 2.50 (two US dollars and fifty cents) for each US$ 1,000.00 (one thousand US dollars) of the principal amount to those investors who agreed to the proposed changes, totaling approximately US$ 252,000.

*******************

www.telemigholding.com.br - 8/13

For further information, please contact:

Telemig Celular Participações S.A.
Investor Relations Department
Oscar Thompson / Renata Pantoja
Phone: (61) 9933-3077 / 3535
E-mail: ri@telepart.com.br

This press release contains forward-looking statements. Such statements are not statements of historical fact, and reflect the beliefs and expectations of the Company's management. The words "anticipates," "believes," "estimates," "expects," "forecasts," "intends," "plans," "predicts," "projects" and "targets" and similar words are intended to identify these statements, which necessarily involve known and unknown risks and uncertainties. Known risks and uncertainties include those resulting from the short history of the Company's operations as an independent, private-sector, entity and the introduction of competition to the Brazilian telecommunications sector, as well as those relating to the cost and availability of financing, the performance of the Brazilian economy generally, the levels of exchange rates between Brazilian and foreign currencies and the Federal Government's telecommunications policy. Accordingly, the actual results of operations of the Company may be different from the Company's current expectations, and the reader should not place undue reliance on these forward-looking statements. Forward-looking statements speak only as of the date they are made, and the Company does not undertake any obligation to update them in light of new information or future developments.

www.telemigholding.com.br - 9/13

OPERATIONAL DATA

www.telemigholding.com.br - 10/13

INCOME STATEMENT (BR GAAP)

www.telemigholding.com.br - 11/13

BALANCE SHEET (BR GAAP)

CASH FLOW (BR GAAP)

www.telemigholding.com.br - 12/13

GLOSSARY OF KEY INDICATORS

I) Average Subscribers

    a) Average subscribers – monthly

     Sum of subscribers at the beginning and the end of the month
2

    b) Average subscribers – quarterly and year to date

Sum of the average subscribers for each month of the period
Number of months in the period

II) Churn Rate (Annualized)

            a) Churn % quarterly

     Sum of deactivations / Sum of average monthly opening subscribers for the 3 months x 12
3

            b) Churn % - year to date

YTD deactivations / Sum of avg monthly opening subscribers since beginning of the year x 12
Number of months in the period

III) MOU – Minutes of Use (Monthly)

Number of total billable minutes for the period / Average subscribers for the period
Number of months in the periods

IV) ARPU – Average Revenue per User

Net service revenues for the period (excluding roaming-in revenues)
Average subscribers for the period

V) Customer Acquisition Cost

(Sum of Marketing salaries, Selling salaries, Consulting (Sales and Marketing),
Commissions, Handsets subsidies, Advertising and promotions,
FISTEL tax (activation tax), less Activation fee for the period)
Number of gross activations in the period

VI) Free Cash Flow

VII) Working Capital Variation

     Working Capital Variation = ( ( Current Assets – ( Cash & Cash Equivalents) –
(( Current Liabilities – ( Short Term Loans and Financing - ( Loan Interest - ( Dividends)

VIII) Interest Coverage Ratio

Interest Coverage Ratio = EBITDA / Interest Paid

IX) Current Liquidity Ratio

Current Liquidity Ratio = Current Assets / Current Liabilities

X) EBITDA

    EBITDA = Operational Revenues - Operational Costs - Operational Expenses* - Bad Debt

* Does not include profit sharing.

www.telemigholding.com.br - 13/13

This press release may contain forward-looking statements. These statements are statements that are not historical facts, and are based on management's current view and estimates offuture economic circumstances, industry conditions, company performance and financial results. The words "anticipates", "believes", "estimates", "expects", "plans" and similar expressions, as they relate to the company, are intended to identify forward-looking statements. Statements regarding the declaration or payment of dividends, the implementation of principal operating and financing strategies and capital expenditure plans, the direction of future operations and the factors or trends affecting financial condition, liquidity or results of operations are examples of forward-looking statements. Such statements reflect the current views of management and are subject to a number of risks and uncertainties. There is no guarantee that the expected events, trends or results will actually occur. The statements are based on many assumptions and factors, including general economic and market conditions, industry conditions, and operating factors. Any changes in such assumptions or factors could cause actual results to differ materially from current expectations.