While mobile users want to obtain software anywhere and anytime without the knowledge of software availability in advance, software providers want to deploy their software to mobile devices without the users' intervention. However, because mobile devices expose special characteristics such as restriction of capability, heterogeneity, mobility, wireless connectivity, and context-orientation, deployment of software or context-aware services on mobile devices is a problematical issue. This work proposes a framework for over the air provider-initiated software deployment on mobile devices (OTA-PSD). Using the OTA-PSD, once new software or software updates are available, by the initiation of the provider, the compatible mobile devices, which have subscribed to the provider, will automatically receive this software with the minimum users' intervention. This framework allows providers to deploy their services on mobile devices based on users' context and device specification. To demonstrate the feasibility of the OTA-PSD, we developed a deployment system based on the OTA-PSD. We successfully demonstrated the deployment of a case study using our deployment system.