Long ago, in the 1500s and 1600s, many professionals were called 'men of the cloth', that is to say, men who dressed in special cloth (clothes). The clothes of their calling, or 'uniforms' as we would call them today, identified them as professionals, whether a baker, a steward, or a clergyman.
By the late 1600s, the meaning had narrowed to mean men of the church, a minister or clergyman who wore the formal garb of the profession. The phrase 'The Cloth' also came to refer to the priesthood at this time.
Today the phrase 'man of the cloth' can be applied to a minister, preacher, or clergyman of any Christian denomination. In recent decades the phrase 'woman of the cloth' has also come into use.