We examined phylogenetic relationships and patterns of stem structural evolution in Eleocharis subgenus Limnochloa, an ecologically and economically important group of tropical to temperate-growing sedges, whose stems serve as the primary photosynthetic organs. We used maximum parsimony, likelihood, and Bayesian inference to develop phylogenetic trees and stochastic mapping and a Markov one-rate model to develop character history reconstructions of stem architecture. A complex history of stem shape evolution characterized by a high degree of homoplasy and rapid rates of change (an average of 13 transitions per character history for about 25 species) was identified across subgenus Limnochloa. Character states transition much more frequently in some lineages than others, but tend to follow a consistent directional pattern of evolutionary change. Our data also suggest that changes in stem shape and anatomy may be associated with speciation events in the subgenus (Pagel's κ = 0.3503, P = 0.04579) and may have some adaptive significance. The potential adaptive roles of stem structural traits are unclear, but may be elucidated by further studies. This work serves as a starting point for future evolutionary studies of stem shape and structure in monocots and provides important background knowledge for further studies of ecological adaptations of Eleocharis.