This club was founded in 1979 as NIAC Mitra. NIAC stood for New International Amusement Center, allegedly a large casino in Surabaya during the 1970s. NIAC was dissolved by its owner, Alexander Wenas, on 24 September 1990.
A phoenix club named Mitra Surabaya was founded in 1993. After relegation to the First Division, the club moved to Palangkaraya, Central Kalimantan and were renamed Mitra Kalteng Putra (MKP) in 1999. At the end of 2001 season, the club was relegated to the Second Division. Financial problems led the club to be loaned to Suryanto Anwar, after which they moved again, to Tenggarong, Kutai Kartanegara, East Kalimantan, where they received its current name. The new ownership had a great impact. At the end of the 2003 season, Mitra Kukar were promoted to the First Division. In the 2005 season, the new owner fully bought Mitra Kukar. By the end of 2007 season, Mitra Kukar succeeded to be promoted to the Premier Division, after finishing first in the First Division. In the 2010–11 Premier Division, Mitra Kukar was promoted to the Indonesia Super League after finishing third in the final round.