Innovations through Enterprise Architecture (EA) require a transformation in public sector’s management. EA has been identified as one of the prime initiatives towards public sector transformation. EA implementation is highly recommended to execute efficient and effective public service delivery. However, building upon several public sector agencies that had implemented these initiatives, EA implementation in Malaysian Public Sector (MPS) was reported as unfavourable. This study aims to identify related issues and challenges towards sustainability of EA implementation. A qualitative research approach was employed in this study. Semi structured interview was held involving five EA experts. From the analysis, six related issues such as (i) absence of the mandate from government to implement EA initiatives (ii) improper EA governance leading to difficulty in managing EA implementation; (iii) absence of EA tool to maintain EA document; (iv) lack of EA awareness (v) lack of EA readiness and (vi) limited knowledge and skills on EA among the team were discerned in sustaining EA practices. With regard to the practical implication, this paper can serve as reference in EA implementation in the public sector.