This letter of intent proposes an experiment to search for an electric dipole moment of the muon based on the frozen-spin technique. We intend to exploit the high electric field, \(E=1{\rm GV/m}\), experienced in the rest frame of the muon with a momentum of \(p=125 {\rm MeV/}c\) when passing through a large magnetic field of \(|\vec{B}|=3{\rm T}\). Current muon fluxes at the \(\mu\)E1 beam line permit an improved search with a sensitivity of \(\sigma(d_\mu)\leq 6\times10^{-23}e{\rm cm}\), about three orders of magnitude more sensitivity than for the current upper limit of \(|d_\mu|\leq1.8\times10^{-19}e{\rm cm}\)\,(C.L. 95\%). With the advent of the new high intensity muon beam, HIMB, and the cold muon source, muCool, at PSI the sensitivity of the search could be further improved by tailoring a re-acceleration scheme to match the experiments injection phase space. While a null result would set a significantly improved upper limit on an otherwise un-constrained Wilson coefficient, the discovery of a muon EDM would corroborate the existence of physics beyond the Standard Model.