Humans and many other hosts establish a diverse community of beneficial microbes anew each generation. The order and identity of incoming symbionts is critical for health, but what determines the success of the assembly process remains poorly understood. Here we develop ecological theory to identify factors important for microbial community assembly. Our method maps out all feasible pathways for the assembly of a given microbiome—with analogies to the mutational maps underlying fitness landscapes in evolutionary biology. Building these “assembly maps” reveals a tradeoff at the heart of the assembly process. Ecological dependencies between members of the microbiota make assembly predictable—and can provide metabolic benefits to the host—but these dependencies may also create barriers to assembly. This effect occurs because interdependent species can fail to establish when each relies on the other to colonize first. We support our predictions with published data from the assembly of the preterm infant microbiota, where we find that ecological dependence is associated with a predictable order of arrival. Our models also suggest that hosts can overcome barriers to assembly via mechanisms that either promote the uptake of multiple symbiont species in one step or feed early colonizers. This predicted importance of host feeding is supported by published data on the impacts of breast milk in the assembly of the human microbiome. We conclude that both microbe to microbe and host to microbe interactions are important for the trajectory of microbiome assembly.