A layered-keyframe-based, presentation recording service provides for presentation recording sessions, the recording of presentations, and the creation of presentation videos. A user records with the user's device the document pages and page annotations, as well audio and video streams, that are presented using the device during the course of a presentation recording session. The pages, annotations and video streams are efficiently and separately recorded as keyframes. These keyframes are used as document, annotation and video layers to create layered keyframes. A presentation video is created from the layered keyframes and the recorded audio stream. Users can then playback presentation videos at a time, place and manner that is available to, accessible by and/or convenient to them.