Cutting-edge sensors and devices are increasingly deployed within urban areas to make-up the fabric of transmission control protocol/internet protocol connectivity driven by Internet of Things (IoT). This immersion into physical urban environments creates new data streams, which could be exploited to deliver novel cloud-based services. Connected vehicles and road-infrastructure data are leveraged in this article to build applications that alleviate notorious parking and induced traffic-congestion issues. To optimize the utility of parking lots, our proposed SmartPark algorithm employs a discrete Markov-chain model to demystify the future state of a parking lot, by the time a vehicle is expected to reach it. The algorithm features three modular sections. First, a search process is triggered to identify the expected arrival-time periods to all parking lots in the targeted central business district (CBD) area. This process utilizes smart-pole data streams reporting congestion rates across parking area junctions. Then, a predictive analytics phase uses consolidated historical data about past parking dynamics to infer a state-transition matrix, showing the transformation of available spots in a parking lot over short periods of time. Finally, this matrix is projected against similar future seasonal periods to figure out the actual vacancy-expectation of a lot. The performance evaluation over an actual busy CBD area in Stockholm (Sweden) shows increased scalability capabilities, when further parking resources are made available, compared to a baseline case algorithm. Using standard urban-mobility simulation packages, the traffic-congestion-aware SmartPark is also shown to minimize the journey duration to the selected parking lot while maximizing the chances to find an available spot at the selected lot.