Nemsadze speelde in de periode 1992–2004 in totaal 69 officiële interlands (nul doelpunten) voor het Georgisch voetbalelftal.[2] Hij maakte zijn debuut voor de nationale ploeg op 2 september1992 in het vriendschappelijke duel tegen Litouwen, dat met 1-0 werd verloren. Hij viel in dat duel na 57 minuten in voor Revaz Arveladze.