Throughout most of human history, the average person died where they were born. They rarely traveled or came across anyone very different than themselves.
When they happened to meet someone from far away, the threat was real - not only were scarce resources at stake, but the lack of shared language, customs, and beliefs created a gulf in social trust signals and behavior.
Beyond that, an invisible menace lurked in each set of strangers: viruses that one isolated group evolved immune system resistance to over hundreds or thousands of years could easily pass to another isolated tribe who had no such protection with devastating results.
So the people groups that survived were cautious, and evolved a subconscious distrust towards the strange and stranger. The people groups who acted without caution are no longer in the gene pool.
While we no longer face such mysterious threats from out-groups in modern times, we still have a powerful vestigial distrust of the other only equaled by our strong affinity for our tribe.