There has been enormous interest about Covering Location Problem (CLP) among both academicians and practitioners around the world. Applications of CLP range from locating fire stations to telecommunications. This paper deals with a special case of CLP where travel times are fuzzy variables. In addition, it has been assumed that the variable cost of locating facilities is a function of the distance between the facility and its farthest assigned node. The objective is to find a solution minimizing the total cost of network In order to be resourceful in finding solutions, a hybrid procedure of Variable Neighborhood Search (VNS) and fuzzy simulation has been used. Numerical experiments showed that our algorithm works well and its robustness has been shown through an example.