Creating key frames during indexing of a trace for responsive trace replay. A method includes identifying responsiveness goal(s) for trace replay, including identifying a target trace section replay time. A portion of execution of executable entit(ies) is replayed based on trace data stream(s). While replaying execution of the executable entit(ies), and based on the identified target trace section replay time, points of interest in execution of the executable entit(ies) are identified. At least one key frame is created for each of the identified plurality of points of interest. Each key frame enables replay of at least one of the one or more executable entities beginning at the key frame.