In Service-Oriented Virtual Organization Breeding Environments (SOVOBEs), services performed by people, organizations and information systems are composed in potentially complex business processes performed by a set of partners. In a SOVOBE, the success of a virtual organization depends largely on the partner and service selection process, which determines the composition of services performed by the VO partners. In this paper requirements for a partner and service selection method for SOVOBEs are defined and a novel Multi-Aspect Partner and Service Selection method, MAPSS, is presented. The MAPSS method allows a VO planner to select appropriate services and partners based on their competences and their relations with other services/partners. The MAPSS method relies on a genetic algorithm to select the most appropriate set of partners and services.