The benefits of records management have been well documented; from preserving evidence and supporting accountability and transparency, to preserving nations' documentary heritage. Governments as with many other organisations have realised the importance of records management for good governance and have put in place policies, programmes and procedures aimed at managing their records effectively and efficiently. In spite of the many benefits that can be derived from records management and efforts made, challenges continue to be reported. This chapter discusses these challenges within the context of the records management programme of the Namibia public sector. The author cites studies conducted by various researchers on records management in a variety of public sector institutions ranging from central government, regional and local authorities and academic institutions. Some recommendations to address a number of the challenges identified are presented.