Akan tetapi, Nainggolan harus pindah ke SPAL di bursa transfer musim dingin dengan status bebas transfer. Namun, pada akhir musim klub yang di musim ini masih berkutat di Serie C Italia itu memutuskan untuk tidak memperpanjang kontrak pemain asal Belgia tersebut.
Sebelum bermain di level senior, Radja Nainggolan sempat memperkuat beberapa kelompok umur Timnas Belgia, seperti U-16, U-19, U-20, dan U-21.
Nainggolan melakoni laga debut di Timnas Belgia senior pada 29 Mei 2009, tepatnya di laga persahabatan kontra Chile yang berkeduahan skor imbang 1-1 untuk kedua tim.
Namun sayang, Nainggolan tidak menjadi pemain andalan di skuad The Red Devils. Pemain yang di musim ini berstatus tanpa klub itu hanya memainkan satu ajang internasional, yakni EURO 2016.
Di ajang yang dihelat di Prancis itu, Nainggolan dan Timnas Belgia itu hanya mampu mencapai babak perempat final. Pasukan Marc Wilmots harus kalah di babak itu dari Wales dengan skor 3-1.