 Žaliūkas was loaned to Hearts from FBK Kaunas in August 2006.He made his competitive debut for Hearts on 26 August 2006 in a 4–1 victory over Inverness Caledonian Thistle, and scored his first goal for the Tynecastle club in a 2–2 draw against St Mirren in December 2006.He earned hero status amongst Hearts fans on 1 April 2007 by scoring a late winner against Edinburgh derby rivals Hibernian at Easter Road.