Pada asalnya, Sukan Asia Tenggara diberi nama Sukan Semenanjung Asia Tenggara atau Sukan SEAP. Pada 22 Mei 1958, semua delegasi dari negara semenanjung Asia Tenggara menghadiri Sukan Asia ke-3 di Tokyo, Jepun untuk melakukan perjumpaan dan telah disetujui banyak pihak untuk mengadakan pertubuhan sukan ini. Sukan SEAP dibentuk konsepkan oleh Laung Sukhumnaipradit iaitu Naib Presiden Komiti Olimpik Thailand pada masa itu. Cadangan ini diterima dan sukan ini dipromosikan kepada negara-negara semenanjung Asia Tenggara. Tujuan Sukan Asia Tenggara adalah bahawa acara sukan serantau akan membantu menggalakkan kerjasama, persefahaman dan menguatkan hubungan antara negara-negara di rantau Asia Tenggara.

Thailand, Burma (kini; Myanmar), Malaya (kini; Malaysia), Laos, Vietnam Selatan, dan Kemboja (juga Singapura menyertai kemudiannya) dijadikan sebagai anggota sukan ini. Kebanyakan negara menyetujui temasya ini diadakan secara dwi-tahunan. Komiti Persekutuan Sukan SEAP mula dibentuk selepas itu.

Sukan SEAP pertama diadakan di Bangkok, Thailand dari 12-17 Disember 1959 dan disertai seramai 527 atlet dan pegawai rasmi dari Thailand, Burma, Malaysia, Singapura, Vietnam Selatan, dan Laos mengambil bahagian dalam 12 jenis sukan.

Sukan SEAP ke-8 pada 1975, Persekutuan SEAP membawa masuk kontinjen negara dari Indonesia dan Filipina. Dua negara itu diterima pada 1977, tahun yang sama yang mana Persekutuan SEAP menukar nama kepada Pertubuhan Sukan Asia Tenggara (SEAGF) dan temasya dwi-tahunan ini dikenali sebagai Sukan Asia Tenggara. Brunei diterima masuk pada Sukan SEA ke-10 di Jakarta, Indonesia, dan Timor-Leste pada Sukan SEA ke-22 di Hanoi, Vietnam.

Sukan SEA ke-23 diadakan di Filipina, yang mana diadakan bermula 27 November dan berakhir 5 Disember 2005, yang menjadi hos temasya dwi-tahunan ini buat kali ketiga.