Bajevski doorliep de jeugdreeksen bij Vardar in zijn geboortestad. Daar speelde hij 15 jaar, waarvan 7 bij het fanionelftal. Daarna begon hij aan een tocht door Europa: in vijf jaar tijd speelde hij in Servië (OFK Belgrado), Hongarije (Győr, Balaton, Ferencváros) en Polen (Górnik Łęczna). Van Polen ging het naar Qatar, waar hij vier maanden voor Al-Ahli speelde. Sinds juli 2007 lag hij in België onder contract bij KV Mechelen. In Mechelen werd zijn contract echter vroegtijdig verbroken in januari 2008. In 2009 speelde hij opnieuw voor Vardar Skopje. Nadien speelde hij nog bij DAC Dunajska Streda en KS Flamurtari Vlorë vooraleer in juli 2011 een contract te tekenen bij het Indonesische Pelita Jaya FC.