There is provided with an encoded digital audio reproducing apparatus including: a reading control portion which reads an encoded audio file having a data part including audio data as a sequence of frames and a size part including size information on each of the frames; a table generating portion which generates a table holding positional information on frames at intervals of a predetermined number of frames in the sequence of frames; a decoding portion which sequentially decodes the audio data from a leading frame to output the decoded audio data; a reproducing portion which reproduces the decoded audio data; and a reproduction start position calculating portion which, in the case where a reproduction request from an arbitrary frame in the audio data is inputted, decides from the table a frame satisfying a positional reference for the arbitrary frame as a reproduction start frame.