I don't have it handy to grab specifics, but Sex at Dawn discusses a couple dozen different cultures in which promiscuity is the norm. Some of those cultures shame the non-promiscuous, to varying extents.

Human society as we currently know it is less than 10,000 years old. That's an incredibly short timescale for major evolutionary changes.