The NA64 electron beam program comprises of a high sensitivity search for visible and invisible decays of the hypothetical dark photon, $A'$, with a goal to either observe the sub-GeV Dark Matter mediator or exclude most of the model parameter space. The visible channel search also includes clarification of the origin of the $^8$Be anomaly observed by the Atomki experiment. The NA64 collaboration further aims to expand its searches with a proposal to use the muon beam at the CERN M2 beam line which will focus on the unique possibility to search for a new scalar or vector states weakly coupled predominantly to muons, e.g. a new Z$_\mu$ gauge boson of L$_\mu$ - L$_\tau$ symmetry, which might explain the long standing muon (g-2)$_\mu$ anomaly. It will also include searches for the Z$_\mu$ as a vector mediator of Dark Matter production. Within the Conventional Beam Working Group of the Physics Beyond Colliders (PBC) study, several projects for the muon beamline (M2) in the CERN North Area were proposed. The different experimental requirements and the various technical feasibility studies performed by the group will be presented together with the combined results of NA64 electron beam run between 2016-2018, its future plans and the muon proposal with its planned searches.