This paper deals with a stochastic version of the simple facility location problem where the demands of customers are random variables. Under the assumption of step function type distribution of demands, the problem is shown to be approximated by a mixed 0–1 linear programming problem. A heuristic procedure is developed to solve the problem, which successfully extends the well known dual-based approach by Bilde & Krarup, and Erlenkotter. Computational results with 20 test problems are presented to demonstrate the effectiveness of the proposed heuristic.