We investigate mortality differentials in Eastern Europe, a region known for its excessively high adult mortality. Our analyses employ a unique longitudinal data set covering the entire population of Bulgaria from the census of 1992 until 1998. It focuses on differences in mortality between Muslims and non-Muslims. We employ multivariate hazards models to investigate ethnic/religious differences. We demonstrate that excess mortality among Turkish Muslims is primarily attributable to their disadvantaged social and economic positions. For young men, Muslims mortality is lower than non-Muslim and the Muslim advantage increases when socioeconomic differences are controlled. An analysis of causes of death suggests that lower consumption of alcohol may contribute to this `Muslimparadox'. However, for older Muslim women, a significant mortality disadvantage remains after controls are imposed. The mortality of Gypsies, whether Muslim or Christian, is very high. The excess extends to nearly every cause of death examined and is not entirely explained by their adverse location on social and economic variables. The cause-of-death analysis reveals an intriguing advantage in suicide mortality for all Muslim groups relative to both Christian groups.