Three-flavor QCD simulation with the O(a)-improved Wilson fermion action is made employing an exact fermion algorithm developed for an odd number of quark flavors. For the plaquette gauge action, an unexpected first-order phase transition is found in the strong coupling regime (β 5.0) at relatively heavy quark masses (mPS/mV∼0.74-0.87). Strong metastability persists on a large lattice of size 123×32, which indicates that the transition has a bulk nature. The phase gap becomes smaller toward weaker couplings and vanishes at β 5.0, which corresponds to a lattice spacing a 0.1fm. These results imply that realistic simulations of QCD with three flavors of dynamical Wilson-type fermions at lattice spacings in the range a=0.1-0.2fm are not possible with the plaquette gauge action. Extending the study to improved gauge actions, we do not observe evidence for first-order phase transition, at least within the (β,κ) range we explored. This suggests the possibility that the phase transition either moves away or weakens with improved gauge actions. Possible origins of the phase transition are discussed. © 2005 The American Physical Society.