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×10^{20} 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.