This paper presents Free Parking System (FPS), a system for assigning free curbside parking spaces to drivers in the cities. FPS has two components: a mobile app running on the drivers’ smart phones that submits parking requests and guides drivers to their parking spaces, and a server that manages the parking assignment process. Unlike existing parking systems, FPS is cost-effective as it does not rely on any sensing infrastructure and reduces parking space contention because it provides individual space assignments to drivers. The main novelty of FPS consists of its parking assignment algorithm, FPA, which combines a system-wide social welfare objective with a modified compound laxity algorithm to minimize the total travel time for all drivers. Furthermore, FPS adapts on-the-fly to new parking requests and to parking spaces occupied by drivers who do not use our system. The simulation results demonstrate that FPA reduces the total travel time by factor of 4 when compared to a baseline that mimics the way people search for parking today. It also reduces the travel time by 42% when compared to a greedy parking assignment algorithm. Furthermore, FPA provides substantial improvements even when many parking spaces are occupied by drivers who do not use FPS.