Mobile Crowd Sensing (MCS) acts as a key component of Internet of Things (IoTs), which has attracted much attention. In an MCS system, participants play an important role, since all the data is collected and provided by them. It is challenging but essential to recruit credible participants and motive them to contribute high quality data. In this paper, we propose a learning-based credible participant recruitment strategy (LC-PRS), which aims to maximize the platform and participants’ profits at the same time via MCS participation. Specifically, the LC-PRS consists of two mechanisms, that a learning-based reward allocation mechanism (L-RAM) first calculates the maximum offered reward for different locations based on the number of participants in each location. Under a budget constraint, the proposed L-RAM prefers to collect sensing data from locations which relatively few data has so far been collected. Furthermore, for each location, we develop a credible participant recruitment mechanism (C-PRM), which employs semi-Markov model and game theory to predict quality of data provided by each participant and to recruit participants based on the predictions and the maximum offered reward calculated by L-RAM. We formally show LC-PRS has the desirable properties of computational efficiency, selection efficiency, individual rationality and truthfulness. We evaluate the proposed scheme via simulation using three real datasets. Extensive simulation results well justify the effectiveness of the proposed approach in comparison with other two methods.