The major focus of this paper is a gender-based analysis of school superintendent decision-making and problem-solving as well as an investigation of contemporary leadership dilemmas. The findings are based on responses from 258 superintendents of K-12 school districts in Delaware, Maryland, New Jersey, New York, and Pennsylvania collected over a period of three years (2009-2011). The researchers also conducted 18 comprehensive qualitative "face-to-face" interviews with self-selected superintendents who responded to the quantitative survey. The intended outcome of this article is for education policy makers, professors, and practitioners to comprehensively examine the extent and degree of various dilemmas confronting the Mid-Atlantic Region school superintendent sample and to evaluate the decision-making and problem-solving approaches used by them. The study results that are presented will serve as valuable references to not only individual superintendents but also to university administrator preparation professors and to state administrator licensure agencies because it is important for all aspiring superintendents to know the various issues associated with education leadership and the personal and professional dilemmas that they need to be prepared to face as they embark on a career to improve schooling in the United States.