A novel approach to visual self-localization in completely unknown environment with a fully unsupervised and computationally efficient algorithm is proposed in this paper. It is based on the recently developed evolving fuzzy classifier (eClass). The problem of self localization and landmark recognition is of extreme importance for designing efficient and flexible land-based autonomous uninhabited vehicles (AUV). The availability of global coordinates, a GPS link, and unrestricted communication is often compromised by a number of factors, such as interference, weather, and mission objectives. The ability to self-localize and recognize landmarks is vital in such cases for an AUV to survive and function effectively. The self-organizing classifier (eClass) is designed by automatic labeling and grouping the landmarks that are detected in real-time based on the image data (video stream grabbed by the camera mounted on the mobile robot, AUV). The proposed approach makes possible autonomous joint landmark detection and recognition without the use of absolute coordinates, any communication link or any pre-training. The proposed algorithm is recursive, non-iterative, one pass and thus computationally inexpensive and suitable for real-time applications. A set of new formulae for on-line data normalization of the data are introduced in the paper. Real-life tests has been carried out in outdoor environment at the Lancaster University campus using Pioneer3 DX mobile robots equipped with a pan-tilt zoom camera and an on-board PC. The results illustrate the viability and flexibility of the proposed approach. Further investigations will be directed towards teams of mobile robots (AUV) performing a task in completely unknown environment (c) IEEE Press