Cikal bakal Telkomsel dimulai di Batam. Proyek percobaan pengoperasian GSM Telkom saat itu dilaksanakan dengan ultimatum ”kejam”. Jika gagal uji coba GSM sebelum ayam berkokok di tahun 1994, Telkom tak akan diizinkan mengoperasikannya.
Ternyata, walaupun sudah diputuskan oleh Menparpostel, Dirjen Postel masih menekan Telkom dengan menginstruksikan agar Telkom menyelesaikan pembangunan GSM di Batam sebelum ayam berkokok tahun 1994 yang artinya awal bulan Januari 1994. Jika tidak dapat menyelesaikan maka izin membangun dan menyelenggarakan GSM akan dialihkan ke pihak swasta. Tanpa membuang waktu kemudian Setyanto menugaskan Garuda Sugardo untuk memimpin proyek telepon seluler GSM ini, khusus untuk proyek perintis di Batam didukung oleh Kepala Wilayah Telekomunikasi Sumatera Barat (yang membawahi Batam), Adek Julianwar, untuk menyiapkan kebutuhan gedung dan raise-floor serta sarana yang diperlukan lainnya, sehingga perangkat GSM dapat dipasang sesuai dengan spesifikasi tekniknya. Surat perintah khusus dikirimkan kepada Adek Julianwar agar mengambil berbagai langkah yang diperlukan untuk pengadaan sarana penunjang instalasi GSM di Batam sesuai waktunya.
Tekanan Dirjen Postel untuk segera menyelesaikan pembangunan GSM juga mendorong Setyanto untuk mengumpulkan para vendor perangkat GSM di Jakarta dan meminta mereka untuk membantu percepatan penyelesaian proyek ini. Setelah itu Setyanto dengan tim keliling Eropa untuk langsung menemui pimpinan perusahaan pembuat GSM di Eropa antara lain Siemens dan Ericsson dan minta dukungan mereka dalam mempercepat membangun GSM di Indonesia dengan tawaran tanpa adanya kontrak terlebih dulu dan statusnya sebagai barang pinjaman. Jika dapat beroperasi dengan baik maka dalam waktu 3 bulan akan dibayar lunas. Mungkin kalau langkah ini dilakukan sekarang, dapat dipastikan KPK akan menangkap Setyanto karena mengadakan peralatan dalam nilai yang besar tanpa melalui proses tender.
Dari semua vendor yang ada, hanya Ericsson (Swedia) yang mempunyai persediaan siap (ready stock) perangkat GSM. Karena itu Ericsson langsung diberikan surat perintah untuk mengadakan perangkat GSM. Hanya saja waktu yang mereka butuhkan empat bulan karena proses pengirimannya memakan waktu. Itu tidak akan cukup untuk mengejar syarat ”sebelum ayam berkokok tahun 1994”, yang artinya maksimal 31 Desember 1993, sudah harus bisa terbukti sistem GSM yang dilakukan Telkom bisa dioperasikan.
Karena itu Telkom harus jemput bola, mengurus sendiri pengiriman perangkatnya dari Swedia ke Batam. Apabila pengiriman melalui Jakarta dulu sesuai jalur yang ada akan memerlukan waktu minimal tiga minggu. Ini akan menjadi masalah karena waktunya mendekati liburan hari raya Natal. Setyanto langsung membuat keputusan agar dikirimkan menggunakan pesawat terbang ke Singapura sebagai tujuan akhir dan dari Singapura dikirimkan ke Batam dengan kapal laut. Untuk ini ia minta bantuan Dirjen Bea Cukai, Soehardjo yang kebetulan juga Komisaris PT Telkom untuk membantu kelancarannya.
Akhirnya tanggal 31 Desember 1993, pembangunan GSM di Batam dapat diselesaikan dengan baik. Walaupun sudah selesai pada awal Januari 1994, namun baru pada bulan September 1994 proyek GSM di Batam diresmikan oleh Prof. B.J. Habibie didampingi Menparpostel ad interim Dr. Harijanto Dhanutirto. Kebanggaan saat itu muncul karena Telkom mampu mendahului Singapura (yang masih menggunakan sistem AMPS) membangun telepon seluler GSM bahkan sinyal GSM Telkom ini dapat ditangkap dengan baik di Bandara Changi.
Untuk menyelenggarakan jasa telepon seluler ini kemudian dibentuklah anak perusahan Telkom, yang dinamakan Telkomsel yang merupakan kependekan dari Telkom Seluler. Namun karena di dalam penyelenggaraan telepon seluler ini juga terdapat pula jasa pelayanan telekomunikasi internasional maka Menparpostel menginstruksikan agar kepemilikan Telkomsel juga diberikan dengan jumlah yang sama kepada PT Indosat. Akhirnya disepakati Telkom memiliki 51,03% dan Indosat 48,97%.
Telkomsel yang resmi didirikan pada tanggal 26 Mei 1995. Setyanto menunjuk Koesmarihati sebagai Direktur Utama dan Garuda Sugardo sebagai Direktur Teknik, yang merupakan perwakilan dari Telkom. Wakil dari Indosat adalah Rudiantara sebagai Direktur Niaga dan Hulman Sijabat sebagai Direktur Keuangan.
Di balik pemilihan lokasi pertama GSM Telkomsel di Batam sesungguhnya Telkom dan Telkomsel mendapat hikmahnya. Karena daerah ini berada di bawah naungan Otorita Batam yang berada di bawah kekuasaan dan pembinaan Prof. B.J. Habibie sehingga tentunya akan dilindungi kepastian bisnisnya dan tidak akan ada intervensi dari pihak lain. Selain itu juga agar di awal pendiriannya, Telkomsel menghindari persaingan “head to head” dengan Satelindo di Jakarta yang juga mendapat izin mengoperasikan sistem GSM. Jika terjadi head to head dengan Satelindo, dikhawatirkan dapat mengusik Satelindo yang sedang menikmati kenyamanan yang sedang mereka peroleh dengan menetapkan harga telepon genggam yang tinggi yakni Rp17 juta. Hal ini karena pelanggan juga harus membeli handset-nya dari Satelindo. Di samping itu Satelindo yang milik putera orang penting di Indonesia memang mendapatkan proteksi yang luar biasa dari pemerintah.
Berdasarkan pengalaman Setyanto saat menjadi Dirut PT INTI yang waktu itu ikut menyelenggarakan pelayanan STKB dengan menyediakan perangkat terminalnya (handset), jika perusahaan harus menyediakan handset-nya akan sangat membebani arus kas karena harus menyediakan perangkatnya tepat waktu di samping itu risiko hilang dari gudang penyimpanan pun sangat besar. Akhirnya Setyanto putuskan dengan memberikan arahan kepada Dirut Telkomsel agar fokus ke bisnis utama yakni menjual trafik atau pulsa, sedangkan pengadaan handset-nya agar dibebaskan, diserahkan ke pihak ketiga. Tanpa disadari langkah ini merupakan liberalisasi ponsel yang pertama di Indonesia.
Dari Batam kemudian pelayanan Telkomsel diperluas ke Pekanbaru, kemudian Medan, karena akses ke lokasi tersebut dari Batam sudah tersedia jaringan transmisi gelombang mikro Trans Sumatra. Setelah beberapa kota besar di Indonesia terpasang GSM Telkomsel baru masuk ke Jakarta, sehingga persaingan dengan Satelindo yang saat itu masih menjual telepon genggam (handset-nya) dengan harga tinggi tak terhindarkan. Karena sistem layanan yang ditawarkan Telkomsel dianggap lebih efisien, dengan membebaskan pelanggan membeli handset-nya sendiri-sendiri sesuai selera, maka Telkomsel kebanjiran pelanggan. Calon pelanggan berbondong-bondong mendatangi loket penjualan Telkomsel.
Satelindo tampaknya berusaha menjegal, melalui Dirjen Pajak, yang juga Komisaris Utama Satelindo. Kemudian muncullah aturan agar setiap kepemilikan ponsel (handset telepon seluler) untuk bisa tersambung ke jaringan telepon seluler harus disertai faktur pajak pembelian. Ternyata kemudian banyak pelanggan yang mengakali aturan ini dengan membeli surat faktur pajak di pasar gelap yang harganya relatif murah.
Ada juga dampak lainnya. Tanpa diperhitungkan sebelumnya, akibat keputusan liberalisasi ponsel yang dilakukan Telkomsel, banyak gerai-gerai ponsel yang bermunculan yang tersebar di seluruh Indonesia. Ini menjadi fenomena tersendiri. Akhirnya Satelindo pun mengikuti tuntutan pasar, mengikuti jejak Telkomsel melakukan liberalisasi ponsel jasa pelayanannya.
Benar kata orang bijak bahwa the journey of a thousand miles begins with one step, karena langkah pertama Telkomsel yang sudah benar ini maka perjalanan Telkomsel selanjutnya lancar dan mampu mengungguli para pesaingnya sampai saat ini. Di samping itu jangkauan jaringan Telkomsel pun lebih luas karena pembangunannya diawali dari luar Pulau Jawa baru kemudian setelah merata mulai masuk ke kota-kota besar di Pulau Jawa.
(Cuplikan dari Buku Fast Learner – Setyanto P. Santosa, Halaman 179-183)