A technique is directed to operating an authentication system. The technique involves receiving an enrollment request to enroll a user in a new authentication procedure in place of an earlier-established authentication procedure. The earlier-established authentication procedure is operative to authenticate the user at a first security level within a range of security levels. The new authentication procedure is operative to authenticate the user at a second security level within the range of security levels, the first security level being at least as high as the second security level within the range of security levels. The technique further involves, in response to the enrollment request, initiating the earlier-established authentication procedure to authenticate the user. The technique further involves, in response to completion of the earlier-established authentication procedure, performing an authentication enrollment operation associated with the new authentication procedure.