Church was the second daughter of Claude and Lucille Church. Her father was a member of the US Army, so she lived in such places as Okinawa, Fayetteville, NC, Sandy, UT, and Colorado Springs, CO before she graduated high school. After graduating, she moved to Dallas to attend college and continued her modeling career. Modeling had her working in cities like Chicago and Paris. In 1988, she moved to Nashville to realize her dreams of becoming a singer.
She has been married to singer-songwriterRodney Crowell since 1998. They met while shooting a music video. During a brief break-up, Crowell wrote the song "Please Remember Me", which later became a hit for Tim McGraw. Later he wrote "Making Memories of Us" for her as a Valentine's Day gift. The song became a major hit for Keith Urban.