Background: It is normally thought that deep corolla tubes evolve when a plant's successful reproduction is contingent on having a corolla tube longer than the tongue of the flower's pollinators, and that pollinators evolve ever-longer tongues because individuals with longer tongues can obtain more nectar from flowers. A recent model shows that, in the presence of pollinators with long and short tongues that experience resource competition, coexisting plant species can diverge in corolla-tube depth, because this increases the proportion of pollen grains that lands on co-specific flowers. Methodology/Principal Findings: We have extended the model to study whether resource competition can trigger the co-evolution of tongue length and corolla-tube depth. Starting with two plant and two pollinator species, all of them having the same distribution of tongue length or corolla-tube depth, we show that variability in corolla-tube depth leads to divergence in tongue length, provided that increasing tongue length is not equally costly for both species. Once the two pollinator species differ in tongue length, divergence in corolla-tube depth between the two plant species ensues. Conclusions/Significance: Co-evolution between tongue length and corolla-tube depth is a robust outcome of the model, obtained for a wide range of parameter values, but it requires that tongue elongation is substantially easier for one pollinator species than for the other, that pollinators follow a near-optimal foraging strategy, that pollinators experience competition for resources and that plants experience pollination limitation.