The ability of mobile robots to sense, interpret and map their environments in human terms is decisive for their applicability to everyday activities hereafter. Bearing this view in mind, we present here, for the first time, an integrated framework that aims: (i) to introduce a semantic mapping method and (ii) to use this semantic map, as a means to provide a hierarchical navigation solution. The semantic map is formed in a bottom-up fashion, along the robot׳s course, relying on the conceptual space quantization, the time proximity and the spatial coherence integrated into the labeled sparse topological map. A novel time-evolving augmented navigation graph determines the semantic topology of the explored environment and the connectivity among the recognized places expressed by the inter-place transition probability. The robot navigation part is addressed through an interface that facilitates human robot interaction. High level orders are passed to the robots and unfolded recursively, in a top-down fashion, into local navigation data. The performance of the proposed framework was evaluated on long range real world data and exhibited remarkable results.