Learn English – Origin of the expression “part and parcel”

Citing Picturesque Expressions by Laurence Urdang, Facts on File Dictionary of Clichés (p.317), and the OED, Ken Greenwald had this comprehensive explanation of the phrase at Wordwizard:

PART AND PARCEL means essential portion or element, integral part, a vital part of a larger entity. <“Traveling was part and parcel of his sales position.”>. In this reduplicative phrase (repetition of an element), which has been common since the 14th century, the nouns ‘part’ and ‘parcel’ are synonyms and have been since the 14th century, ‘part’ being the older word (11th century) and ‘parcel’ (14th century) the newer. The alliteration and tautology/redundancy in the expression serve to emphasize the importance of a constituent to the whole. The expression has been used as a legal term from the mid-16th century on, principally for clauses of a law and for parts of a landholding. It didn’t start to be used in its present figurative sense until about 1800. ‘Part or parcel’ and ‘part nor parcel’ have also been used since the 16th century.

Earliest reference from OED:

1535-6 ‘Act 27 Henry VIII,’ c. 11 “This present Act, and euery PART AND PARCEL therof, shall extend [etc.]. Ibid. c. 26 The. . . . Lordships . . . to be PART AND PARCELL of the same hundred [of Wesebery].”

Earliest I can find via Google Books (from A Christian Directorie Guiding Men to Their Salvation, 1585):