Didirikan pada tahun 1999 setelah terbentuknya Kabupaten Lembata pada 12 Oktober 1999 sebagai hasil pemekaran Kabupaten Flores Timur, Askab PSSI Kabupaten Lembata dibentuk sebagai badan pengurus klub ini. Sebulan setelah berdirinya Kabupaten Lembata, mereka mengikuti ajang El Tari Memorial Cup 1999 di Kabupaten Ende. Skuad tersebut beranggotakan Ryan Walili, Ansi Lensa, Inosius Sanjaya, Jou Kasim, Mukin, Yoseph Lanjar, Husain Atamuan, Gomez Luan, Salem Mustafa, dan Herri Rungkat.[3]
Persebata untuk pertama kalinya meraih prestasi terbaik di El Tari Memorial Cup 2022 (sebagai Liga 3 Nusa Tenggara Timur), sebagai tuan rumah mereka berhasil mencapai final namun sayangnya kalah dari Perse Ende setelah bermain imbang 2–2 dan kalah adu penalti 2–3 di Stadion Gelora 99, Lembata.[4]
Pada El Tari Memorial Cup 2025 (sebagai Liga 4 Nusa Tenggara Timur), mereka kembali meraih gelar juara kedua setelah kalah di final atas Bintang Timur Atambua dengan skor 2–4 lewat adu penalti setelah bermain imbang 2–2 di waktu normal di Stadion Oepoi, Kupang. Namun, mereka berhak mewakili Nusa Tenggara Timur bersama dua klub lain, yakni Bintang Timur Atambua sebagai juara dan Perseftim Flores Timur sebagai juara ketiga.[5]
Pada fase grup Liga 4 2024–2025 fase nasional, di putaran pertama mereka berhasil menjadi juara Grup P dengan hasil 2 kali menang dan 1 kali seri, dan memastikan lolos ke babak kedua, seluruh pertandingan digelar di Stadion Kompyang Sujana dan Stadion Ngurah Rai, Denpasar.[6] Pada putaran kedua yang digelar di tempat yang sama, mereka kembali lolos sebagai juara Grup X dengan hasil 2 kali menang dan 1 kali seri, sehingga melaju ke putaran ketiga.[7] Pada tanggal 14 Mei 2025, Persebata memastikan promosi ke Liga Nusantara untuk pertama kalinya dalam sejarah mulai musim depan setelah hasil imbang dengan Persika Karanganyar 1–1 di Stadion Sultan Agung, Bantul pada laga terakhir babak ketiga Grup B di fase nasional Liga 4. Pada babak keempat, Persebata tergabung dalam Grup 1 bersama Persitara Jakarta Utara, Tri Brata Rafflesia, dan Perseden Denpasar.[8]
Untuk memainkan laga kandangnya di Liga Nusantara, mereka memilih bermarkas di Stadion Oepoi, Kupang, hal ini dikarenakan belum siapnya Stadion Gelora 99 di Lembata dan fasilitas pendukungnya.[9]
Pemain
Per 15 April 2025.
Catatan: Bendera menunjukkan tim nasional sesuai dengan peraturan kelayakan FIFA. Pemain bisa saja memiliki lebih dari satu kewarganegaraan non-FIFA.
.jpg)
