This paper deals with video-based face recognition and tracking from a camera mounted on a mobile robot companion. All persons must be logically identified before being authorized to interact with the robot while continuous tracking is compulsory in order to estimate the person's approximate position. A first contribution relates to experiments of still-image-based face recognition methods in order to check which image projection and classifier associations give the highest performance of the face database acquired from our robot. Our approach, based on Principal Component Analysis (PCA) and Support Vector Machines (SVM) improved by genetic algorithm optimization of the free-parameters, is found to outperform conventional appearance-based holistic classifiers (eigenface and Fisherface) which are used as benchmarks. Relative performances are analyzed by means of Receiver Operator Characteristics which systematically provide optimized classifier free-parameter settings. Finally, for the SVM-based classifier, we propose a non-dominated sorting genetic algorithm to obtain optimized free-parameter settings. The second and central contribution is the design of a complete still-to-video face recognition system, dedicated to the previously identified person, which integrates face verification, as intermittent features, and shape and clothing color, as persistent cues, in a robust and probabilistically motivated way. The particle filtering framework, is well-suited to this context as it facilitates the fusion of different measurement sources. Automatic target recovery, after full occlusion or temporally disappearance from the field of view, is provided by positioning the particles according to face classification probabilities in the importance function. Moreover, the multi-cue fusion in the measurement function proves to be more reliable than any other individual cues. Evaluations on key-sequences acquired by the robot during long-term operations in crowded and continuously changing indoor environments demonstrate the robustness of the tracker against such natural settings. Mixing all these cues makes our video-based face recognition system work under a wide range of conditions encountered by the robot during its movements. The paper concludes with a discussion of possible extensions.