Uterine arteriovenous malformation is a rare condition characterized by abnormal connections between the arteries and veins in the uterus. This condition, though uncommon, can have severe implications for women's reproductive health and requires prompt diagnosis and appropriate treatment. This case report presents a nulliparous 20-year-old virgin patient with congenital arteriovenous malformation who wanted to preserve her fertility and was refusing all vaginal approaches for diagnosis and treatment. She was admitted to our facility and had two attacks of profuse vaginal bleeding, in which she lost 3 L of blood. She was diagnosed by a pelvic CT scan and treated by bilateral uterine artery coil embolization. To our knowledge, this is the first reported case of a patient presenting with profuse vaginal bleeding who was both nulliparous and a virgin.