Abstract: Valet parking system consists of thoughtfully crafted yet easily mastered software applications which are easy to use for technologically less oriented people to use ride on demand service. Our findings have made us understand the need of on demand valet service system in the metropolitan cities of India due to the increasing population and the subsequent increase in the vehicle traffic. This project introduces a novel algorithm that provides a valet parking system and develops a architecture based on the Fire base Cloud Messaging(FCM) technology. This paper proposed a system that helps users find parking solutions at the least cost based on new performance metrics to calculate the user parking cost by considering the distance and time. This cost will be used to offer a solution of finding an available valet service provide upon a request by the user and a solution of suggesting a new valet service provider if the current valet service provider does not accept the request or nobody is available to serve at the moment. The simulation results show that the algorithm helps in providing on demand valet service to the users and minimizes the users hassle is finding parking in the real time. We will also successfully implement the proposed system in the real world.Keywords: car parking, valet, machine learning, k nearest neighbor, android, java, etc