In this paper, we discuss the challenges experienced by Kenyan public universities in implementation of e-learning and recommend possible solutions towards its successful implementation. In the last few years, most Kenyan public universities have adopted e-learning as a new approach to teaching and learning. However, the implementation challenges faced by these universities have continued to impact negatively on its effective utilization. This paper presents the findings from a survey of 148 staff of three Kenyan public universities who are currently using e-learning in blended mode approach. The purpose of this study was to investigate the challenges hindering the implementation of e-learning in Kenyan public universities. Data was collected through questionnaires, in-depth interviews and document analysis. The findings reveal that e-learning comes with some challenges that must be addressed by Kenyan public universities before successful implementation can be realized. However, the benefits and opportunities presented by e-learning far outweigh the challenges. The paper finally recommends some possible solutions that public universities could embrace towards successful implementation of e-learning.