The ever-increasing number of mobile device users has also raised the users’ expectation of mobile services accordingly. This phenomenon has given pressures to the mobile service providers to improve their services in order to stay competitive in the market. The service oriented approach is seen to be a promising scheme for mobile services. This paper presents mobile service oriented architectures for Nearest-Neighbor (NN) queries that are classified into five categories, namely (i) intermittent query mobile services, (ii) continuous query mobile services, (iii) context-aware mobile services, (iv) continuous moving object query mobile services, and (v) data broadcast mobile services. These services incorporate query, location and context-aware services, ontological context model, and broadcast. The proposed architectures are concerned with mobile services for clients on the move requesting services based on their current location, which is arguably the most important feature in a wireless environment. Furthermore, we also discuss the Quality-of-Service (QoS) requirement for mobile services in which request latency time is one of the most important parameters to consider. Some analytical models for query latency measurement are presented and the results are compared with the simulation experiments.