A recording medium and a method of recording data on the recording medium are provided. The method of recording data includes recording a transport stream on the recording medium. The transport stream is composed of one or more predetermined units, each predetermined unit starting with at least one transport packet for carrying navigation information used to manage subsequent transport packets. The first packet of the transport packet carries only the navigation information including program clock reference (PCR) information and does not carry presentation data.