Persebaya was founded by Paijo and M. Pamoedji on June 18, 1927. At its inception, Persebaya was named Soerabhaiasche Indonesische Voetbal Bond (SIVB). It was the Indonesian version of a club named Sorabaiasche Voetbal Bond (SVB), which was founded in 1910 and composed of Dutch football players in Surabaya.
On 19 April 1930, SIVB, along with VIJ Jakarta, Bandung BIVB (now Persib Bandung), MIVB (now PPSM Magelang), MVB (PSM Madison), VVB (Persis Solo), and PSM (PSIM Yogyakarta), participated in the birth of the Football Association of Indonesia (PSSI), in a meeting held in Yogyakarta Societeit Hadiprojo. M. Pamoedji represented the SIVB in the aforementioned meeting. A year later, the first competition between the city/union was organized. SIVB made it into the final union competition in 1938, but ended up losing against VIJ Jakarta.
When the Dutch lost to Japan in 1942, almost all the players in the SIVB were indigenous Indonesian, with a small amount of Chinese players. SIVB reached the finals that year, before being beaten by Persis Solo. Finally, in 1943, SIVB was renamed to SIVB Persibaja (Football Association of Indonesia Soerabaja). In this era, Persibaja had Dr. Soewandi as its chairman. At that time, Persibaja won three titles in 1950, 1951, and 1952.
In 1960, SIVB Persibaja was renamed to Persebaya (Surabaya Football Association). Persebaya was larger than PSMS Medan, PSM Makassar, Bandung or Persija Jakarta. Persebaya had won two championship titles in 1978 and 1988, and finished in the second place seven times in 1965, 1967, 1971, 1973, 1977, 1987, and 1990.
When PSSI united football teams in the competition titled "Galatama Liga Indonesia" in 1994, they achieved a few milestones. Persebaya Indonesia achieved the league title in 1997. Persebaya were relegated on the 2002 season, but immediately return to the top flight as the First Division champion on 2003, and then immediately crowned as the Premier Division champion on the 2004 season. With this second championship win, Persebaya became the first Indonesian football team to be a two-time champion in Indonesia since Liga Indonesia Era.
One player considerably remembered is Eri Irianto, a national soccer team player in the 1990s. Irianto died while confined in a hospital on April 3, 2000, after a sudden illness while playing against PSIM Yogyakarta in the 1999–2000 Liga Indonesia Premier Division. Eri's name was later used as the name of the guesthouse/mess hall of Persebaya which was inaugurated on April 25, 1993.
Persebaya played their home matches in Gelora Bung Tomo Stadium, which is also known as GBT. The stadium itself opened on August 6, 2010. The rest of the sports complex are indoor stadium and a mosque. This stadium used mostly for football matches and is a new home stadium of Persebaya, replacing Gelora 10 November Stadium.