We present a search for long-lived particles (LLPs), produced in kaon decays, that decay to two muons inside the ICARUS neutrino detector. This channel would be a signal of hidden sector models that can address outstanding issues in particle physics such as the strong CP problem and the microphysical origin of dark matter. The search is performed with data collected in the Neutrinos at the Main Injector (NuMI) beam at Fermilab corresponding to 2.41×1020 protons-on-target. No new physics signal is observed, and we set world leading limits on heavy QCD axions, as well as for the Higgs portal scalar among dedicated searches. Limits are also presented in a model-independent way applicable to any new physics model predicting the process K→π+S(→μμ), for a LLP S. This result is the first search for new physics performed with the ICARUS detector at Fermilab. It paves the way for the future program of LLP searches at ICARUS. Published by the American Physical Society 2025