Education is essential for developing labor in Indonesia. One type of formal education is "madrasah" education that has been historically significant in Indonesia which adds depth in Islamic subjects in addition to basic subjects. These graduates may become important as the "Sharia" industry continues to boom in Indonesia. However, "madrasah" education has shown weak labor market performances compared to general education, in terms of wages and unemployment. This may stem from a weak learning process in madrasahs which is against the 4th Sustainable Development Goals (SDGs) about equitable education. With limited studies on madrasah education performance in the labor market, using 2014 Indonesia Family Life Survey, we find: (1) "madrasah" education choice is influenced by parent's education and appeals to low-income families, (2) "madrasah" graduates have lower probability of working compared to general education graduates, (3) return of "madrasah" education is lower compared to general education. Therefore, policies should improve "madrasah" education through improvement of teachers and institution quality, support and funding for private madrasahs, and supporting "Madrasah Kejuruan."