Whoever was going to be appointed king had to be a Jew of Israelite descent (as opposed to a convert). It would be considered unseemly to place an outsider in charge of the nation.
The reason for this is that the leader is going to rule the people, judge the people, tax the people, and more. His perspective is going to be different if he's actually one OF the people, born and bred. (Also, the people have to accept his rule, which they are less likely to do if he is perceived as an outsider imposed upon them.)
The mishna in tractate Sotah (41a) says that, in the Second Temple era, King Agrippa I was worried about this mitzvah because he wasn't Jewish on his father's side. The people reassured him by saying, “You are our brother! You are our brother!” However, the gemara there (41b) says that even though he was a “good guy,” Agrippa wasn't really entitled to the job and the people who reassured him, well-meaning though they may have been, were in violation of this mitzvah.
This mitzvah applies when the Jews occupy their land. In the Talmud, it is discussed in tractate Sotah (41a) and in Yevamos (45a) and codified in the Mishneh Torah in the first chapter of Hilchos Melachim. This mitzvah is #362 of the 365 negative mitzvos in the Rambam’s Sefer HaMitzvos.