A video data recording device for sufficiently protecting privacy even before a mask target enters into a screen. The video data recording device includes a reference information storage unit in which reference information including predetermined features is recorded; a video data acquisition unit which acquires video data and sequentially outputs the video data to a video buffer; a similarity determining unit which compares newest video data and the reference information, and extracts partial information determined to be similar to the reference information from the newest video data; a relation determining unit which compares video data output to the video buffer before the newest video data, and the partial information determined to be similar, and extracts partial information determined to be related to the partial information determined to be similar; and an imaging recording I/F unit which records the video data and the related information related to the partial information in a recording medium.