This club was founded in 1979. They were renamed Niac Mitra or Mitra Surabaya in the 1990s. 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 H Suryanto Anwar, after which they moved again, to Tenggarong, Kutai Kartanegara, East Kalimantan, where they were finally renamed Mitra Kukar. 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.