We report the first search for dark sectors performed at the NA64 experiment employing a high energy muon beam and a missing energy-momentum technique. Muons from the M2 beamline at the CERN Super Proton Synchrotron with a momentum of 160 GeV/c are directed to an active target. The signal signature consists of a single scattered muon with momentum <80 GeV/c in the final state, accompanied by missing energy, i.e., no detectable activity in the downstream calorimeters. For a total dataset of (1.98±0.02)×1010 muons on target, no event is observed in the expected signal region. This allows us to set new limits on the remaining (mZ′,gZ′) parameter space of a new Z′ (Lμ−Lτ) vector boson which could explain the muon (g−2)μ anomaly. Additionally, our study excludes part of the parameter space suggested by the thermal dark matter relic abundance. Our results pave the way to explore dark sectors and light dark matter with muon beams in a unique and complementary way to other experiments. Published by the American Physical Society 2024