Distinct organisms can become integrated into a single evolutionary unit via mutualistic symbiosis with strictly vertical transmission, where a host inherits the symbionts from its parents. A possible way to establish such mutualism is the evolutionary transition from a looser relation, horizontally transmitted mutualism, where a host gathers the partners from its surroundings. However, the transition between the two types of mutualism is still unclear because they differ in how to prevent free-riders from exploiting. In particular, horizontally transmitted mutualism requires "partner choice", a mechanism to associate with only cooperative symbionts, but as relying on vertical transmission the choosiness will no longer be favored because hosts tend to inherit limited partners. Here, I theoretically examined the coevolutionary dynamics of partner choice by hosts and cooperation by symbionts. My study shows that even with the loss of partner choice during the transition, mutualism usually persists by vertical transmission without a gap. Also, depending on the manner of partner choice, mutualism can break down in the middle of the transition and the two types of mutualism are disconnected. Those provide new insights into how the major transition in evolution occurs and why there are many types in symbiotic systems.