Paglia was born in Endicott, New York, the eldest child of Pasquale and Lydia Anne (née Colapietro) Paglia. All four of her grandparents were born in Italy. Her mother immigrated to the United States at five years old from Ceccano, in the province of Frosinone, Lazio, Italy. Additionally, Paglia has stated that her father's side of the family were from the Campanian towns of Avellino, Benevento, and Caserta. Paglia attended primary school in rural Oxford, New York, where her family lived in a working farmhouse. Her father, a veteran of World War II, taught at the Oxford Academy high school, and exposed his young daughter to art through books he brought home about French art history. In 1957, her family moved to Syracuse, New York, so that her father could begin graduate school; he eventually became a professor of Romance languages at Le Moyne College. She attended the Edward Smith Elementary School, T. Aaron Levy Junior High and William Nottingham High School. In 1992 Carmelia Metosh, her Latin teacher for three years, said, "She always has been controversial. Whatever statements were being made (in class), she had to challenge them. She made good points then, as she does now." Paglia thanked Metosh in the acknowledgements to Sexual Personae, later describing her as "the dragon lady of Latin studies, who breathed fire at principals and school boards".
She took a variety of names when she was at Spruce Ridge Camp, including Anastasia (her confirmation name, inspired by the film Anastasia starring Ingrid Bergman), Stacy, and Stanley. A crucially significant event for her was when an outhouse exploded after she poured too much lime into the latrine. "That symbolized everything I would do with my life and work. Excess and extravagance and explosiveness. I would be someone who would look into the latrine of culture, into pornography and crime and psychopathology... and I would drop the bomb into it".
For more than a decade, Paglia was the partner of artist Alison Maddex. Paglia legally adopted Maddex's son (who was born in 2002). In 2007 the couple separated but remained "harmonious co-parents," in Paglia's words, who lived two miles apart.
Paglia identifies as transgender and stated that she has "never identified at all with being a woman".