Pada musim 1994-95, PSSI menyatukan Perserikatan dan Galatama untuk membentuk Liga Indonesia. Semen Padang memenuhi syarat untuk tampil sebagai salah satu dari 34 peserta Divisi Utama pada musim itu.
Semen Padang tergabung di Wilayah Barat dan mengakhiri musim pada peringkat kelima, hanya setingkat di bawah zona kelolosan menuju putaran kedua.
Seperti halnya di Galatama, Semen Padang tidak mencatat prestasi signifikan di Divisi Utama. Semen Padang pertama kali lolos ke babak gugur pada musim 1998–99 setelah menjadi peringkat kedua di Wilayah Barat di bawah PSMS Medan, namun harus tersingkir di putaran kedua setelah kalah saing dari Persebaya Surabaya dan PSIS Semarang.
Pada musim 2002, SP berhasil menjuarai Wilayah Barat dengan tim yang diperkuat oleh pemain seperti Ellie Aiboy, Erol Iba, Carlos Renato Elias, dan Rommy Diaz Putra.
Mereka berhasil melaju ke semifinal, namun harus menelan kekalahan lewat adu penalti dari Petrokimia Putra yang diperkuat oleh Widodo C. Putro, yang kemudian menjuarai liga (juga lewat adu penalti).
Pada musim 2004 yang berformat satu divisi, Semen Padang buat pertama kalinya terlempar dari sepuluh besar; mereka mengakhiri musim di peringkat ke-15 dari 18 tim, hanya satu tingkat dan satu poin di atas rival sepulau PSPS Pekanbaru yang terdegradasi.
Tiga musim kemudian, Semen Padang mengakhiri musim di peringkat ke-16 di Wilayah Barat dan gagal terpilih menjadi salah satu tim yang ikut dalam Liga Super Indonesia, kasta tertinggi profesional baru yang akan bergulir pada tahun 2008-09; Divisi Utama otomatis menjadi kasta kedua.
Untuk pertama kalinya sejak dua musim pertamanya, Semen Padang bermain di divisi kedua.
Di bawah asuhan kepala pelatih asal Moldova Arcan Iurie pada musim 2009–10, Semen Padang berhasil mengamankan satu tiket promosi ke Liga Super sebagai peringkat ketiga, dengan mengalahkan Persiram Raja Ampat.