Methods, apparatus, systems, and articles of manufacture to perform speed-enhanced playback of recorded media are disclosed. Example apparatus to playback media disclosed herein comprise at least one memory, machine-readable instructions, and processor circuitry to execute the machine-readable instructions to parse an audio frame included in the media to determine a number of skip bytes included in the audio frame, compare the number of skip bytes to a threshold, associate the audio frame with a plurality of candidate frames identified in the media when the number of skip bytes satisfies the threshold, and calculate a speed-enhanced playback rate for the media based on the plurality of candidate frames identified in the media.