Finding a free parking space in the metropolitan areas during rush hour is time consuming and it leads to traffic congestions and air pollution. Wireless Sensor Network (WSN) can be used to obtain information related to the parking condition requiring very little installation and maintenance costs. In this work, we present the design and implementation of an outdoor parking system based on Wireless Sensor Networks (WSNs), received signal strength (RSS) and pattern recognition algorithms to effectively find free parking spaces. Simulation and experiment results show good performance in the verification of the parking system. XBee-PRO 900HP-S3B modules with high performance and low power consumption were used. These modules support the IEEE-802.15.4 protocol for communication in the 900 MHz band and can be configured in different network topologies. The received signal strength (RSS) was measured to form fingerprints for the parking spaces availability (busy or vacant). Kalman filters were implemented to improve RSS which varies due to the effects of short-term fading. The parking spaces availability was evaluated with different classification algorithms in the WEKA environment with results up to 85%.