A self-localization device including a storage unit that associates and stores a plurality of reference images and imaging positions of the plurality of respective reference images and an operation unit that periodically estimates a self-location of a movable body based on information obtained from a sensor included in the movable body, wherein the operation unit determines, when estimation of the self-location fails, a moving distance from a latest self-location obtained from successful estimation of the self-location before the estimation fails using the information from the sensor and extracts a plurality of the reference images belonging to a range of the moving distance from the latest self-location and searches the plurality of extracted reference images for images similar to a current image captured by an imaging device included in the movable body to estimate the self-location of the movable body.