A service-oriented network (SON) is defined as a set of networked devices which collaborate to fulfill a complex ubiquitous service (u-service). Thus, the service quality of a u-service request highly depends on the quality of the devices and the communication links of SON. The utility-based approach is typically employed to evaluate the quality of a SON. Many existing SON construction approaches adopt a generic utility function. However, a generic utility function is insufficient to reflect the QoS needs of best-effort u-services and real-time u-services because they have quite different QoS objectives. In this paper, a multi-objective utility-based SON construction approach is proposed. Specific utility functions are defined to meet the distinct QoS needs of different types of u-services in the proposed approach. The simulation results show that the proposed multi-objective approach has 2∼8 and 1∼4 times better than the traditional single-objective approach in service quality and real-time performance, respectively.