Mutualistic symbioses are considered to evolve from parasitic relationships. Vertical transmission, defined as the direct transfer of infection from a parent organism to its progeny, has been suggested as a key factor causing reduction of symbiont virulence and evolution of mutualism. On the other hand, there are several mutualistic associations without vertical transmission, such as those between plants and mycorrhizal fungi, legumes and rhizobia, and some corals and dinoflagellates. It is expected that all mutualisms evolve perfect vertical transmission if the relationship is really mutualistic, because hosts may fail to acquire symbionts if they do not transmit the symbionts by vertical transmission. We have developed a mathematical model to clarify the conditions under which mutualistic symbiosis without vertical transmission should evolve. The evolution may occur when and only when (i) vertical transmission involves some costs in the host, (ii) the symbiont suffers direct negative effects if it exploits the host too intensively, (iii) the host establishes the ability to make use of waste products from the symbiont, and (iv) the mechanism of vertical transmission is controlled by the host. We also clarify the conditions under which mutualistic symbiosis with vertical transmission evolves.