This paper considers the maximum covering facility location and network design problems with uncertainty, and presents comprehensive optimization models. The problem consists of locating a predefined number of facilities and optimizing the underlying transportation network in such a way that total covered demand points are maximized. The two-stage stochastic optimization approach is applied to resolve the uncertainty which typically appears in the model’s key parameters such as demands, costs, and traveling times. The uncertain parameters are characterized with a given finite number of discrete scenarios. Accordingly, the objective function minimizes the expected penalty costs, link construction costs, and facilities fixed costs, while the relative regret in each scenario is bounded. Incorporating uncertainty into the mathematical model increases its complexity by far. However, based on the specific structure of the problem, we show that all decisions can be made at one stage and so, we can reduce the number of constraints and variables. Although the improved formulation in terms of computational efforts is more convenient to solve, the problem is still challenging to solve and cannot be effectively handled by means of traditional methods. Therefore, hybrid solution algorithms based on well-know meta-heuristics are proposed to solve the model and computational experiments are reported.