Rehabilitation of denuded patches using perennial grasses has been used extensively in semi-arid environments of Kenya. However, weeds continue to pose an enormous challenge to the success of many rehabilitation programmes. The aim of this study was to identify the common weeds that pose a challenge to rehabilitation success and establish the grass-weed interactions in rehabilitated areas of a semiarid environment in Kenya. A survey questionnaire was administered to capture the farmers’ perception on the most problematic weeds and the challenge they pose to rehabilitation programmes. Experimental plots were laid out under simulated rainfall (sprinkler system). Three perennial grasses; Cenchrus ciliaris, Eragrostis superba, and Enteropogon macrostachyus, were used. These grasses were sown along ox-ploughed micro-catchments as pure stands and two grass mixtures and monitored at three phenological stages; early vegetative (15cm), elongation (30cm) and reproduction (60cm) representing high, medium and low grazing intensities respectively. Results from this survey showed Ipomoea kituensis posed the greatest challenge to rehabilitation programmes. Results also showed an inverse relationship in biomass yields between the weeds and established grasses across the three phenological stages. These results strongly suggest that selective weeding of rehabilitated semi-arid environments is critical for the success of rehabilitation programmes in semi-arid Kenya.