Through the areas of health and employment, this study examined the disjunction between policy and practice with regards to HIV/AIDS-related discrimination in Indonesia. The primary centres for data collection were Jakarta and Bali, where it was found that the contradictions between international commitments and written internal policies supported for forms of arbitrary discrimination against People Living with HIV/AIDS (PLWHA). This paper argues that for effective change to occur, the cultural mindset of service providers in the health care and employment sectors need to be changed through integrating institutional support and educational training.