The outer Solar System hosts a vast population of small icy bodies, considered to be primitive remnants from the planet formation epoch. Early thermal and collisional processes affected such planetesimals to varying degrees depending on the time scale and dynamics of early planet growth. Hence, key information about early planet formation processes in proto-planetary disks are recorded in icy-rocky bodies, ranging from comets to dwarf planets. Recent observations have shown that many large trans-Neptunian objects (TNOs) exhibit features of volatile compounds in their surface spectra. These include mainly ices of water and smaller abundances of methane, ethane and ammonia, as well as Pluto’s N2-CO-CH4 tenuous atmosphere. I will present calculations of the early evolution of icy-rocky bodies formed beyond the “snow” line. The volatile composition and interior structure of these objects may change considerably due to internal heating and/or collisional modification prior to settling in their current dynamical niches. This may impose an additional composition gradient to that inherent from the disk’s physico-chemical evolution. I will show several results regarding longevity of stratified structures, potential surface variations and bulk retention of volatile organic compounds.