It was an expression originating in eastern europe in the 12th century. Jews were not allowed to live within the town walls, or pale. Anything beyond the pale wwas deemed to be threatening or suspect.
In English usage, it probably dates from the early English occupation of Ireland. A pallisade (or fence) was constructed around Dublin to keep the Irish out (and in). Thus, to be 'beyond the pale' (pale being short for pallisade) was to be Irish/Catholic/definitely not one of 'us'.