As the number of Mobile Web Services (MWS) with different specifications has increased, the task of discovering the relevant ones becomes more challenging in a mobile environment. The challenges include mobile devices constraints and web service descriptions itself. The issues can be considered from the aspect of mobile device’s performance, diversity of available MWS specifications and lack of enriched MWS descriptions. In order to address these issues, this paper presents an enhancement of semantic-based MWS discovery framework for discovering the most relevant MWS that takes into consideration of Non-Functional Properties (NFPs) in web service descriptions. In our work, the matchmaking algorithm with enhanced similarity measure is presented. Semantic MWS profiles are annotated semantically as a WSMO-Lite profile with a RESTbased architecture. The experimental validation and statistical analysis demonstrates that the proposed framework can effectively discover relevant MWS according to the various user requirements. It can be concluded that using the proposed framework, there is a significant improvement in the effectiveness of semantic-based discovery for MWS in mobile computing environments.