Paula met associate pastor Randy White in 1987 while attending Damascus Church of God in Maryland, which was headed by his father. According to the book "Holy Mavericks", meeting this third-generation preacher was a turning point in her life. The two divorced their spouses in 1989 and married each other a year later, Paula becoming step-mother to his children. Shortly thereafter they moved to Tampa, Florida, and started "Without Walls International Church." On August 23, 2007, Randy White announced that he and Paula were divorcing. According to "The Christian Post," White says the divorce was amicable, and they remain friends.