The study examined the records management practices in the major oil marketing companies (OMC) in Uganda. The aim was to ascertain the extent to which oil companies meet legal and regulatory requirements, as should be underpinned by effective records management for achieving their operational and strategic goals. The paper applies the perception of different levels of managers in 10 OMC to assess their records management capacity. Through structured interviews, the study investigated the records management legal framework, existing policy and regulations, ICT initiatives and their alignment to records management requirements, and the records management challenges faced. Results reveal that OMC face daunting challenges, including the ability to meet legal compliance to create and retain records in both paper and electronic format, inadequate records identifiers and access guidelines, a continuing need for storage space for growing volume of records and a pressing need for trained records staff. The paper concludes that records management should be supported with corporate policy, adoption of international records management standards, skilled people and streamlining storage as measures for the OMC to undertake to strengthen the management of their records to respond to customer needs more directly and effectively and open up communication channels and share information with the oil and gas sector regulating institutions.