A media processing engine selectively transcodes only a portion of the media clips to be included in a personalized media program and generates playback data that allows seamless playback of the personalized media program. The media processing engine analyzes initial playback data associated with the media program that indicates the media clips needed to generate the personalized media program. The media processing engine identifies one or more transitions between media clips in the personalized media program and determines specific segments of those media clips that are associated with the identified transition(s). The media processing engine performs transcoding operations with the determined segments of the media clips to generate one or more transition clips. The media processing engine then updates the initial playback data to indicate that the transition clip(s) should be played during the corresponding transition(s) between the associated media clips.