A tape storage device which disregards a fault in recording of data on a tape recording medium is provided. The tape storage device which sequentially records data, is characterized by including: a recording section which records a data freshness degree on a tape recording medium, in association with new data to be newly recorded, the data freshness degree being information indicating how new thenew data is with respect to already-recorded old data; a determining section which determines whether or not a fault occurs in recording on the tape recording medium performed by the recording section; a reading section which reads a faulty portion freshness degree when it is determined that the fault occurs, the faulty portion freshness degree being the data freshness degree of a faulty portion on the tape recording medium; and a skip recording section which allows the recording section to record a data freshness degree higher than the faulty portion freshness degree, immediately before the faulty portion.