The story
The expression appears to have surfaced in the 16th century, allegedly a literal translation of Plato's Republic. In 1545, William Turner wrote a version of the expression in the Rescuing of Romish Fox: "Byrdes of on kynde and color flok and flye allwayes together." One can, however, also compare the expression to Ecclesiasticus (Sirach) 27:9: "Birds resort unto their like."
Etymology from Wiktionary, CC BY-SA 4.0.