Sewaktu pasaran telefon bimbit diperluaskan pada 1995, Celcom menaik taraf ke perkhidmatan GSM900 lalu bertumbuh dengan pesat untuk menjadi syarikat telefon mudah alih terbesar di Malaysia sebelum Maxis.

Ketika Krisis Kewangan Asia pada tahun 1997, Celcom turut terjejas. Ada pendapat yang mendakwa bahawa pemilik Celcom iaitu Tan Sri Tajudin Ramli menghadapi kemelut hutang dan pegangan saham beliau di dalam Celcom dirampas oleh Danaharta, syarikat penstrukturan semula aset negara. Kegagalan melangsaikan hutang beliau mengakibatkan kepentingan kawalan terhadap Celcom dijual kepada Telekom Malaysia, pengendali talian tetap milik kerajaan pada tahun 2003. Telekom Malaysia seterusnya menggabungkan Celcom dengan anak syarikat pengendali perkhidmatan mudah alihnya TMTouch melalui pengambilalihan songsang terhadap TMTouch.

Celcom asalnya tersenarai dalam Bursa Malaysia, namun menjadi syarikat persendirian setelah bergabung dengan Telekom Malaysia.

Dalam satu kes, pihak pengurusan awal Celcom didapati bertanggungjawab oleh satu panel timbang tara di Switzerland kerana melanggar persetujuan yang ditandatangani bersama DeTeAsia, sebuah unit Deutsche Telekom, pada tahun 2002.

Tribunal itu memutuskan bahawa Celcom diwajibkan untuk membayar DeTeAsia AS$177.2 juta hutang pokok tambah AS$16.2 juta faedah serta kos guaman dan timbang tara yang lain, maka jumlahnya RM740 juta yang perlu dibayar.

Penstrukturan semula Celcom yang diterajui oleh TM berjaya memulihkan prestasi Celcom dan meningkatkan daya saing di dalam negara dan di peringkat antarabangsa.

Pada 28 September 2007, Telekom Malaysia mengumumkan rombakan semula unit komunikasi mudah alihnya termasuk Celcom, di mana Celcom dikumpulkan di bawah TM International yang menempatkan beberapa unit mudah alih milik TM yang lain di luar negara, lalu menjadikannya entiti perniagaan berasingan. Penstrukturan semula siap pada suku pertama 2008 dan unit perniagaan baru ini disenaraikan dalam Bursa Malaysia pada suku kedua 2008. TM International dinamakan semula sebagai Axiata sebagai sebuah konsortium telekomunikasi di Asia Tenggara.

Sejak proses pemulihan prestasi dijalankan, syarikat dikatakan telah berjaya meningkatkan pencapaiannya sehingga berjaya mencatatkan pertumbuhan positif mengikut sukuan tahunan selama 23 sukuan berturut-turut.[1]