The Chia-yi area in southwestern Taiwan is a region of relatively high seismicity. Frequent earthquakes of various magnitudes in the shallow crust provide valuable information for understanding the regional seismotectonic environment. In this study, we use strong-motion records from the 22 October 1999, ML 6.4 Chia-yi earthquake sequence to determine the focal mechanisms based on a criterion combining the P-wave polarity and the cross correlations between recorded and synthetic waveforms. A recent 3D structural model for the study region is used, and to ensure the computational efficiency, a database is established for the Green’s functions obtained by the finite-difference method. Optimal focal depths and fault-plane solutions are obtained through a grid-search scheme driven by the genetic algorithm to further improve the efficiency. We apply this approach to determine the focal mechanisms and centroid depths of the small and moderate events in the Chia-yi earthquake sequence. Results show dominant strike-slip and thrust mechanisms that are in good agreement with previous results based upon P-wave first-motion polarities and moment-tensor inversions. This highly automatic and efficient approach will enable the determination of focal depths and fault-plane solutions immediately following the occurrence of small- to moderate-sized earthquakes.