The Miyako and Yonaguni horses are native horses in Okinawa. Here, we evaluated their genetic relationship using microsatellite data and Kiso horses, which have four subpopulations, as a reference population for evaluating this relationship. Microsatellite data from 35 Miyako, 78 Yonaguni, and 172 Kiso horses were evaluated using the STRUCTURE software for analyzing multilocus genotype data to investigate the population structures and their underlying relationship. The results of the STRUCTURE analysis were stable when ΔK was 2, suggesting that the Okinawan horses are different from the Kiso horses. Moreover, the results were also stable when ΔK was 6; the sample was then divided into four subpopulations of the Kiso horses and two Okinawan horse breeds. However, the diagrams from the STRUCTURE analysis were unstable when ΔK was 3. These results suggest that the genetic relationship of the Okinawan horse breeds may be close, similar to that among the subpopulations of the Kiso horses.