A valuable medium handling apparatus configured to handle a valuable medium, the valuable medium handling apparatus comprising: a first memory device having tamper resistance; a second memory device configured to store pieces of software of a plurality of kinds; and a processor configured to execute the pieces of software, wherein the first memory device is provided with: a first memory area configured to store pieces of verification information used for verification of validity of the pieces of software as a list which enables a search for the verification information by version of the software; and a second memory area configured to store identification information for identifying a piece of verification information of the version of the software from the list that is allowed to be executed, and each of the pieces of verification information includes an identifier of the version and a verification value calculated based on a valid piece of software corresponding to the identifier, the pieces of software include an update application configured to update a current version of a different piece of software to a new version, and the processor is configured to execute the update application to store a new version of the software in an area different from an area of the second memory device where a current version of the software is stored, add a piece of verification information of the new version of the software to the list, and rewrite the identification information to enable the new version of the software to be executed. a first memory device having tamper resistance; a second memory device configured to store pieces of software of a plurality of kinds; and a processor configured to execute the pieces of software, wherein the first memory device is provided with: a first memory area configured to store pieces of verification information used for verification of validity of the pieces of software as a list which enables a search for the verification information by version of the software; and a second memory area configured to store identification information for identifying a piece of verification information of the version of the software from the list that is allowed to be executed, and a first memory area configured to store pieces of verification information used for verification of validity of the pieces of software as a list which enables a search for the verification information by version of the software; and a second memory area configured to store identification information for identifying a piece of verification information of the version of the software from the list that is allowed to be executed, and each of the pieces of verification information includes an identifier of the version and a verification value calculated based on a valid piece of software corresponding to the identifier, the pieces of software include an update application configured to update a current version of a different piece of software to a new version, and the processor is configured to execute the update application to store a new version of the software in an area different from an area of the second memory device where a current version of the software is stored, add a piece of verification information of the new version of the software to the list, and rewrite the identification information to enable the new version of the software to be executed. store a new version of the software in an area different from an area of the second memory device where a current version of the software is stored, add a piece of verification information of the new version of the software to the list, and rewrite the identification information to enable the new version of the software to be executed. <EOS>