The OED's first citation is 1551, from Thomas Becon, A Fruitful Treatise of Fasting, which describes how Satan "setteth forth him selfe in his true colours". It's also in Shakespeare, Henry IV Pt 2 (1600) act 2 scene 2: "How might we see Falstaffe bestow himself to night in his true colours, and not our selues be seene?"
The sense of "colours" meaning livery (or some other show of allegiance) is older than Becon. But there are also a lot of metaphorical senses for "colour" that may be relevant.
The OED's definition of "colour" sense II.7.a is "Apparent or de facto legal authority or status, esp. as opposed to that actually granted or established. Frequently with negative connotations, suggesting that the authority is used as a pretext for illegal or corrupt behaviour (cf. sense 8). Chiefly in colour of authority, colour of law, colour of office. Now chiefly U.S." This goes back to 1325
Sense II.8 is "Outward appearance; show, aspect, or semblance of something, esp. as justifying a particular judgment, course of action, etc. Frequently, esp. in later use, with the implication that the appearance is false and used as a pretext. Now chiefly in legal contexts (see sense 7a)." This also goes back to 1325 with several late medieval/early modern uses.
There are various similar senses. None of this indicates the exact origin of the phrase, but you ask for the earliest example. It's clear "true colours" could mean some (often false or misleading) sign of authority or status, with various expressions about appearing, displaying, etc, these colours.
Reference: "colour | color, n.1". OED Online. March 2021. Oxford University Press. https://www-oed-com.nls.idm.oclc.org/view/Entry/36596?rskey=mb4ZyY&result=1&isAdvanced=true (accessed March 25, 2021).