Network function (NF) virtualization is a promising way for service providers to improve configurability of the offered network services. First, NFs and their corresponding flows can be embedded in the substrate network in an automated way. Second, the modularity offered by the description of a service as a composition of NFs and their interconnecting virtual links, enables tuning of the service's logical structure. A major challenge with respect to the management of these environments is the placement of service requests in the physical infrastructure, comprising NFs that can only be instantiated on particular hosts, due to latency, legislation, or hardware-related constraints. These location constraints are known to complicate the resource allocation. This paper proposes two service placement algorithms with better coordination between the composition and embedding phases. We formulate the combined service embedding and chain composition problem as an integer linear program and then, propose a fast heuristic based on greedy chain selection that iteratively adds virtual NF chains to the composition and embeds them at the same time. Simulation experiments show that the proposed cross-layer optimization can significantly increase the acceptance ratio and reduce the embedding cost.