Malawi is a global leader in the design and implementation of progressive HIV policies. However, there continues to be substantial attrition of people living with HIV across the “cascade” of HIV services from diagnosis to treatment, and program outcomes could improve further. Ability to successfully implement national HIV policy, especially in rural areas, may have an impact on consistency of service uptake. We reviewed Malawian policies and guidelines published between 2003 and 2013 relating to accessibility of adult HIV testing, prevention of mother-to-child transmission and HIV care and treatment services using a policy extraction tool, with gaps completed through key informant interviews. A health facility survey was conducted in six facilities serving the population of a demographic surveillance site in rural northern Malawi to investigate service-level policy implementation. Survey data were analyzed using descriptive statistics. Policy implementation was assessed by comparing policy content and facility practice using pre-defined indicators covering service access: quality of care, service coordination and patient tracking, patient support, and medical management. ART was rolled out in Malawi in 2004 and became available in the study area in 2005. In most areas, practices in the surveyed health facilities complied with or exceeded national policy, including those designed to promote rapid initiation onto treatment, such as free services and task-shifting for treatment initiation. However, policy and/or practice were/was lacking in certain areas, in particular those strategies to promote retention in HIV care (e.g., adherence monitoring and home-based care). In some instances, though, facilities implemented alternative progressive practices aimed at improving quality of care and encouraging adherence. While Malawi has formulated a range of progressive policies aiming to promote rapid initiation onto ART, increased investment in policy implementation strategies and quality service delivery, in particular to promote long-term retention on treatment may improve outcomes further.