Background: Child marriage is associated with adverse reproductive health outcomes, and the practice is still alarmingly common. Together with efforts to end child marriage, it is essential to provide adequate health care to already married adolescents. However, to date there has been very limited research on health care-seeking practices among married adolescents in Nepal. Method: The study was conducted in a rural part of Dang District situated in the Mid-western region of Nepal. We combined thirteen individual interviews and four focus group discussions with 17–20 years old women who had married before the age of 18 years and individual interviews with 10 key informants. Results: Pressure to give birth early, limited autonomy, and little knowledge about reproductive health issues make married adolescents vulnerable to risky pregnancies. Early-married women face a range of barriers to use existing health services including work overload, transport and distance to health care facilities, qualities of services, verbal abuse by health care providers, and shyness and embarrassment. Conclusion: Women who marry and become pregnant during adolescence face a number of barriers that limit their access to health care services and they need more attention from the health services and policy makers. More youth friendly health services and education about sexual and reproductive health should be key elements in strategies to address the health issues of early-married women and adolescent girls.