Our belief systems are shaped by social processes, such as observations and influence, and by cognitive processes, such as the drive for internal coherence. These processes steer how individual beliefs evolve and become connected. The resulting belief networks contain both causal and associative links, including spurious ones, such as stereotypes. Here, we develop an agent-based model of belief networks that demonstrates how two basic mechanisms -- social interaction and a drive for internal coherence -- can give rise to such stereotypes without any underlying reality. We further demonstrate how stereotypes, when coupled with shared group identity, can give rise to affective polarization, even in the absence of ideological conflicts.