JLQCD collaboration recently started the $N_f=3$ QCD simulations with the $O(a)$-improved Wilson fermion action employing an exact fermion algorithm developed for odd number of quark flavors. It is found that this theory has an unexpected non-trivial phase structure in the $(beta,kappa)$ plane even at zero temperature. A detailed study is made to understand the nature of the observed phase transitions and to find the way of avoiding untolerably large lattice artifacts associated with the phase transition.