An authentication apparatus includes an input unit which inputs information on a user's fingerprint, an enrolled-image storage which stores a plurality of enrolled images, namely a plurality of fingerprint images, to be verified against a fingerprint image generated by the input unit, and an authentication unit which authenticates the user's fingerprint in a manner such that verification of the fingerprint image against the plurality of enrolled images stored in the enrolled-image storage is performed sequentially in two stages. In the two stages in the verification performed in the authentication unit, enrolled images to be used in the subsequent stage are selected, in the earlier stage thereof, by verifying the fingerprint image against the plurality of enrolled images, and then the user's fingerprint is identified by verifying the fingerprint image against the selected enrolled images in the subsequent stage.