We know that Jews have soul mates: people whom they are destined to marry. Do non-Jews have people they are destined to marry?
The Midrash (Bereishis Rabbah 68:4, and other places) tells a story involving R. Yosei ben Chalafta and a Roman lady, where he tells her that since the six days of creation Hashem occupies Himself with making matches and redistributing wealth ("the daughter of A will marry B; the wife of C will marry D; the assets of E will go to F"); she mocks this and claims that "I could do the same"; she attempts to pair off her slaves, only to find that none of the matches work out, forcing her to admit that "there is no G-d like yours - your Torah is true, beautiful and praiseworthy."
(In a similar vein, there is a popular story about R. Yitzchak Abarbanel having a similar discussion with the king of Castile, which leads to a mixup in which the crown prince is forced to marry an old woman instead of the young one whom the king had selected. Though I don't know whether it's a true story, or where the original source is.)
The implication, then, seems to be that this applies across the board, to Jews and non-Jews alike.
It goes for ALL souls non-jews and Jews.. Everyone has soul mates.. Adam was a non-jew and he has a soulmate :)