In this work we present a local search algorithm for the single row facility location problem. In contrast to other local search algorithms for the problem, our algorithm uses an exponential neighborhood structure. Our computations indicate that our local search algorithm generates solutions to benchmark instances of the problem whose costs are on average within 2% of costs of optimal solutions within reasonable execution time.