Was there such a time? A quick google gives me, for trees, http://en.wikipedia.org/wiki/Evolutionary_history_of_plants#... "The early Devonian landscape was devoid of vegetation taller than waist height." and "The first plants to develop this secondary growth, and a woody habit, were apparently the ferns, and as early as the middle Devonian one species, Wattieza, had already reached heights of 8 m and a tree-like habit.",

Comparing that with http://en.wikipedia.org/wiki/Evolution_of_fungi "A rich diversity of fungi is known from the lower Devonian Rhynie chert", and lower Devonian = early Devonian, I very tentatively conclude fungi precluded trees. Given that, I (not hindered by much specific knowledge of the subject) expect that fungi breaking down cellulose co-evolved with trees.