We consider the problem of predicting and learning the efficiency of navigation tasks being performed by a robot in an initially unknown or partially known, unstructured environment. Predicting the efficiency of a task is a crucial problem in unstructured environments as it enables the robot(s) to decide whether it is feasible to perform the task under the current environment conditions and within its available resources such as battery power. This problem is non-trivial as robot's performance changes during operation based on its operational conditions, available battery change, etc. In this paper, we have addressed this problem by using a learning-based technique that the robot uses to predict its expected efficiency for performing a new task based on the task's similarity and recentness with previously performed tasks. Experimental results show that our proposed technique can successfully predict the efficiency of a task from previous task experiences and this prediction gets better with number of tasks performed. We have also shown empirically that our model is robust to changes in environmental conditions such as localization and wheel slip noise1.