Era penjajahan

Pada tahun 1882, didirikan sebuah badan usaha swasta pembekal perkhidmatan pos dan telegraf. Perkhidmatan komunikasi kemudian dikonsolidasikan oleh Kerajaan Hindia Belanda ke dalam jawatan Post Telegraaf Telefoon (PTT).Sebelumnya, pada tarikh 23 Oktober 1856, bermula Operasi perkhidmatan perkhidmatan telegraf elektromagnet pertama yang menghubungkan Jakarta (Batavia) dengan Bogor (Buitenzorg). Pada tahun 2009 momen bersejarah tersebut dijadikan sebagai patokan hari lahir PT. Telkom Indonesia.

PN Postel

Pada tahun 1961, status jawatan diubah menjadi Perusahaan Negara Pos dan Telekomunikasi (PN Postel). Kemudian pada tahun 1965, PN Postel dipecah menjadi Syarikat Negara Pos dan Giro (PN Pos & Giro (Kini PT. (Persero) Pos Indonesia)) dan Syarikat Negara Telekomunikasi (PN Telekomunikasi).

Perumtel

Pada tahun 1974, PN Telekomunikasi diubah namanya menjadi Perusahaan Umum Telekomunikasi (Perumtel) yang menyelenggarakan jasa telekomunikasi nasional maupun antarabangsa. Tahun 1980 semua saham PT Indonesian Satellite Corporation Tbk. (Indosat) diambil alih oleh Kerajaan Republik Indonesia menjadi Badan Usaha Milik Negara Indonesia (BUMN) untuk menyelenggarakan Jasa Telekomunikasi antarabangsa, terpisah dari Perumtel. Pada tahun 1989, ditetapkan undang-undang Nombor 3 Tahun 1989 tentang Telekomunikasi, yang juga menetapkan peranan swasta dalam penyelenggaraan telekomunikasi.

PT. Telekomunikasi Indonesia (Persero)

Pada tahun 1991 PERUMTEL berubah bentuk menjadi Syarikat Perseroan (Persero) Telekomunikasi Indonesia atau PT. (Persero) Telkom Indonesia berdasarkan Peraturan Pemerintah (PP) RI Nombor 25 Tahun 1991.

PT. Telekomunikasi Indonesia Tbk

Pada tarikh 14 November 1995 dilakukan Penawaran Umum Perdana saham Telkom. Sejak itu saham Telkom tercatat dan tersenarai dalam Bursa Saham Jakarta (BEJ), Bursa Efek Surabaya (BES), Bursa Saham New York (NYSE) dan Bursa Saham London (LSE). Saham Telkom juga tersenarai tanpa pencatatan di Bursa Saham Tokyo.

Tahun 1999 ditetapkan undang-undang Nombor 36 Tahun 1999 tentang Penghapusan Monopoli Penyelenggaraan Telekomunikasi. Memasuki abad ke-21, Kerajaan Indonesia melakukan diregulasi di sektor telekomunikasi dengan membuka persaingan pasaran bebas. Dengan demikian, Telkom tidak lagi memonopoli telekomunikasi Indonesia.

Tahun 2001 Telkom membeli 35% saham Telkomsel dari PT Indosat sebagai sebahagian daripada pelaksanaan penstrukturan industri perkhidmatan telekomunikasi di Indonesia yang ditandai dengan penghapusan kepemilikan bersama dan kepemilikan silang antara Telkom dan Indosat. Sejak bulan September 2002 terjadi duopoli penyelenggaraan telekomunikasi tempatan.

Pada 23 Oktober 2009, Telkom melancarkan "New Telkom" ("Telkom baru") yang ditandai dengan penggantian identiti syarikat.