Balaj begon bij Vllaznia Shkodër en maakte in zijn eerste volledige seizoen (2009/10) direct 17 doelpunten. Na een mislukt seizoen in Turkije bij Gençlerbirliği waarvoor hij slechts eenmaal in actie kwam, keerde hij terug in Albanië waar hij in het seizoen 2011/12 voor Tirana 16 doelpunten maakte. Hij werd gecontracteerd door het Tsjechische Sparta Praag wat hem in het seizoen 2013/14 verhuurde aan Jagiellonia Białystok uit Polen. Balaj speelde vervolgens een half jaar voor Slavia Praag en kwam begin 2015 bij Rijeka uit Kroatië. Voor die club maakte hij 18 doelpunten en medio 2016 werd hij door het Russische Terek Grozny aangetrokken.