In mobile business, context information is utilised to select services mostly tailored to a user’s current situation and preferences. In existing context-aware service selection approaches, a service utility is determined by comparing its non-functional properties with current context information but without considering its integration in a service composition. This may cause suboptimal selection results, as context information and thus the determined utility of a certain service are usually dependent on its preceding and succeeding services. The latter we denote as context interdependencies. In this paper, we investigate how the effects of context interdependencies can be modelled for the context-aware service selection at planning time (i.e. before starting to accomplish a service composition). To develop this approach, we use the concept of states to model context information for the selection. In our evaluation, we find that our approach leads to superior results compared to current context-aware service selection approaches.