Ngày 22/5/1958, các nước Đông Nam Á tham dự Đại hội Thể thao châu Á lần thứ III ở Tokyo, Nhật Bản, Phó Chủ tịch Ủy ban Olympic Thái Lan khi đó là Laung Sukhumnaipradit đã đề xuất và được các nước Đông Nam Á nhất trí thành lập một tổ chức thể thao của Đông Nam Á với tên gọi ban đầu là Liên đoàn Thể thao Bán đảo Đông Nam Á (The South East Asian Peninsular Games Federation hay SEAP Games Federation). Liên đoàn Thể thao Đông Nam Á sẽ tổ chức hai năm một lần vào năm lẻ một đại hội thể thao khu vực nhằm mục đích:

- Tăng cường tình hữu nghị, tình đoàn kết và sự hiểu biết lẫn nhau giữa các nước trong khu vực ASEAN.
- Nâng cao không ngừng thành tích, kỹ thuật, chiến thuật các môn thể thao cho vận động viên để có cơ sở tham gia Đại hội Thể thao Á châu và Olympic.

Thái Lan, Miến Điện (ngày nay là Myanma), Mã Lai (ngày nay là Malaysia), Lào, Việt Nam Cộng Hòa trước đây và Campuchia (Singapore thêm vào sau đó khi tách ra khỏi Malaysia để trở thành quốc gia độc lập vào ngày 9/5/1965) là các nước sáng lập. Ủy ban Liên đoàn SEAP Games được thành lập vào tháng 6 năm 1959 tại Bangkok thủ đô Thái Lan. Các nước sáng lập đã thông qua điều lệ của Liên đoàn và bầu ra Ban chấp hành. Ông Parahát Saruxatiara, Chủ tịch Uỷ ban Olympic Thái Lan, được bầu làm Chủ tịch Liên đoàn Thể thao Đông Nam Á đầu tiên.

SEAP Games đầu tiên được tổ chức tại Bangkok từ 12-17/12/1959 với hơn 527 vận động viên và quan chức thể thao đến từ Thái Lan, Miến Điện, Malaysia, Singapore, Việt Nam và Lào tham dự trong 12 môn thể thao.

Tại SEAP Games lần thứ 8 tổ chức vào năm 1975, Liên đoàn SEAP đã xem xét kết nạp thêm Indonesia và Philippines. Hai nước này chính thức được kết nạp năm 1977. Cùng năm đó, Liên đoàn SEAP đổi tên thành Liên đoàn Thể thao Đông Nam Á (South East Asian Games Federation, SEAGF), và sự kiện thể thao này cũng đổi tên theo thành Đại hội Thể thao Đông Nam Á. Brunei được kết nạp vào SEA Games thứ 10 tại Jakarta, Indonesia, và Đông Timor được kết nạp tại SEA Games thứ 22 tại Hà Nội, Việt Nam.