The muon anomalous magnetic moment measurement has, for more than a decade, been a long-standing anomaly hinting the physics beyond the Standard Model (BSM). The recently announced results from muon $g-2$ collaboration, corresponding to 3.3$sigma$ deviation from Standard Model value (4.2$sigma$ in combination with previous measurement) are strengthening the need for new physics coupled to muons. In this letter, we propose a novel scenario in which Standard Model (SM) is augmented by an axion-like particle (ALP) and vector-like fermions. We find that such a model admits an excellent interpretation of recent muon $g-2$ measurement through quantum process featuring ALP interacting with muons and newly introduced fermions. Previously proposed explanations with ALPs utilize interactions with photons and/or SM fermions. Therefore, in this letter we complement and extend such scenarios. We also discuss collider prospects for the model as well as the possibility that ALP is long lived or stable dark matter (DM) candidate.