Early formation . Founded in 1999 after the establishment of
Lembata Regency on 12 October 1999 as a result of the separation from
East Flores Regency, the
PSSI Lembata Regency Association was formed as the governing body of this club. After a month of the founding of Lembata Regency, they participated in the 1999 El Tari Memorial Cup in
Ende Regency. The squad consists of Ryan Walili, Ansi Lensa, Inosius Sanjaya, Jou Kasim, Mukin, Yoseph Lanjar, Husain Atamuan, Gomez Luan, Salem Mustafa, and Herri Rungkat.
Liga 3 and Liga 4 era Persebata for the first time had the best achievement at
2022 El Tari Memorial Cup (as Liga 3 East Nusa Tenggara), as hosts they managed to reach the final but unfortunately lost to
Perse Ende after drawing 2–2 and losing on penalties 2–3 at the
Gelora 99 Stadium, Lembata. In the
2025 El Tari Memorial Cup (as Liga 4 East Nusa Tenggara), they again achieved the runner-up title after losing in the final to
Bintang Timur Atambua with a score of 2–4 in the penalty shootout after drawing 2–2 in normal time at the
Oepoi Stadium,
Kupang. However, they have the right to represent East Nusa Tenggara with two other clubs, namely Bintang Timur Atambua as champion and
Perseftim East Flores as third place. In the second round held at the same venued, they again qualified as Group X winners with a result of 2 wins and 1 draw, advancing to the third round. On 14 May 2025, Persebata secured promotion to
Liga Nusantara for the first time in their history from
2025–26 season after draw against
Persika Karanganyar 1–1 at
Sultan Agung Stadium in
Bantul, which was the last match in Group B due to difference goal. They managed to advance to the fourth round with the status of second place in the group. In the fourth round, Persebata was included in Group A along with
Persitara North Jakarta,
Tri Brata Rafflesia, and
Perseden Denpasar. They managed 3 draws with 4 goals scored and 4 conceded, but failed to advance to the finals as they finished 2nd position in their group. They were also unbeaten throughout the competition in 12 matches. To play their home games in Liga Nusantara, they chose to base themselves at the Oepoi Stadium in Kupang, this was due to the lack of readiness of the Gelora 99 Stadium and supporting facilities in Lembata. However, it was not used because the Liga Nusantara was finally held at a centralized venue.
Liga Nusantara era In the
2025–26 Liga Nusantara season, they only managed to survive for one season, and the following season, they were relegated back to
Liga 4 after losing in the relegation play-offs. Their final decisive match ended in defeat against
Persikutim United with a score of 0–2 at UHS Stadium,
Surakarta on 2 February 2026. ==Players==