This paper proposes a self-adaptive mobile web service (MWS) discovery approach based on the modified negative selection algorithm (M-NSA) to improve the effectiveness and accuracy of MWS discovery in dynamic mobile environment. The main contributions of this work are the service relevance learning model and a MWS matchmaking algorithm that it is capable of changing as soon as the discovery demonstrates the feasibility of attaining improved effectiveness or accuracy. This is achieved by transforming the two stages of modified negative selection algorithm (M-NSA) into service relevance and self-adaptive matchmaking, respectively. The proposed approach is evaluated in terms of both binary and graded relevance. After an experiment with the largest MWS dataset, the proposed approach records better results in comparison with the state-of-the-art approaches. This is owing to the self/nonself discrimination mechanism, in addition to the decent parameter analysis, and the use of more comprehensive information that covers the entire discovery space.