Paula was born on April 5, 1968 and was pretty much raised in Rockport, Massachussetts. Cole was always certain that music would eventually become what her life revolved around. Her father, Jim, used to be in a polka band playing the bass and also earned a Ph.D. in entomology, but always played music, whether around the house or at weekly gigs. Stephanie, Cole's mother is an artist and her older sister, Irene, works in San Francisco, California as a nurse.

Cole's high school years were filled with tumult and odd experiences. She at one time wanted to be on the cheerleading team, but ended up breaking a bone in her foot and had to wear a wooden shoe throughout an entire year of school. She was teased and soon after wrote her beautifully sad, "Bethlehem" (which would eventually find its way on Cole's debut album, Harbinger) for which she sings "...everyday I dream of leaving." The following year, she made the cheerleading squad and according to her, "It sucked."

Before graduating, the straight-A and Class President Cole also became the Homecoming Queen. After high school, Cole enrolled at Berklee College of Music in Boston. There, she fed her interest in jazz and also met her her boyfriend and fellow musician Seyi Sonuga.Soon she was fortunate to find herself touring alongside Peter Gabriel during his Secret World Tour after Sinead O'Connor bowed out. Gabriel had heard the demos of Cole's then unreleased Harbinger and immediately had her replace O'Connor.
1994 brought the release of Cole's Harbinger on the now defunct label, Imago (once fellow Berklee alumna Aimee Mann's label as well). Commercially, the album wasn't a top ten success, but some of Cole's best songs were showcased with this magnificent release. Happy Home, a song Cole dedicates to her mother at many of her concert performances, tells the story (in my eyes) of having to raise a family and putting one's own feelings and thoughts on the shelf in order to see the family through. Hitler's Brothers describes the horrid racism in our society and the awesome I Am So Ordinary depicts the seeing of a lover with another. All the songs are beautifully written and executed with the finest sounds of piano, percussion and Paula's hollow and airy voice.
In 1995, Cole was again, touring. She accompanied Melissa Etheridge on several shows and also sang with her, Joan Osborne, Jewel, and Sophie B. Hawkins during VH-1's Duets. In late 1996, This Fire, Cole's current release, which she also produced, was reaching music stores and air waves with its hit single, Where Have All The Cowboys Gone?. With a song structure consisting of heavy percussion and Cole's muffled voice compromising that she "...will wash the dishes while you go have a beer...", Where Have All The Cowboys Gone? seemed to have come out of nowhere and was topping Billboard's music charts for weeks.

Riding high on the flames of This Fire Cole accompanied Sarah McLachlan, Sheryl Crow, Abra Moore, Fiona Apple, Joan Osborne, and many talented women in last summer's Lilith Fair, an annual concert event celebrating women in music as envisioned by McLachlan. Cole's performances stole the show and allowed her to become even more recognized.

Just recently, Cole was nominated for seven Grammys, including Producer Of The Year, an achievement Cole considers to be an honor, even more so above the others. As well she should, considering Cole was the first woman ever to be nominated for such a category. She ended up walking away with one Grammy, for Best New Artist. Aretha Franklin, one of Cole's musical idols presented her with the award.

Currently, Cole is touring with Lilith Fair and H.O.R.D.E. There are upcoming dates slated with her opening for Matchbox 20. She hopes to get back in the studio and put another album out in 1999. Meanwhile, she's keeping herself occupied touring, remixing (one of Feelin' Love was just done), and feeding the inner fires of all life.