In this paper, a novel approach to visual self-localization in an unknown environment is presented. The proposed method makes possible the recognition of new landmark without using GPS or any other communication links or pre-training. An image-based self-localization technique is used to automatically label landmarks that are detected in real-time using a computationally efficient and recursive algorithm. Real-time experiments are carried in outdoor environment at Lancaster University using a real mobile robot Pioneer 3DX in order to build a map the local environment without using any communication links. The presented experimental results in real situations show the effectiveness of the proposed method.