Setelah lulus kuliah di tahun 1990, Paula pindah ke San Fransisco dan kerja di took roti sambil cari-cari kesempatan bikin rekaman. Paula akhirnya teken kontrak dengan label Imago pada 1992. Album pertama "Hardbinger" dirilis dua tahun kemudian. Namun, beberapa bulan setelah dirilis Imago bangkrut dan hampir tidak ada promosi untuk "Hardbringer".
Untungnya, Peter Gabriel mendengar album itu dan suka. Peter sendiri yang menghubungi dan ngajak Paula jadi backing/duet vokal di konser "Secret World Tour" dari 1993 sampai 1994. Sejak itu nama Paula Cole makin dikenal banyak orang. Dia mulai sering tur bareng-bareng musisi-musisi hebat seperti Melissa Etheridge, lagu yang paling saya suka dari dia "Come to My Window", dan Sarah McLachlan, yang ngetop dengan lagu "Angel".
Karir Paula mencapai puncaknya saat merilis album kedua "This Fire" di bulan Oktober 1996. Album yang diproduserinya sendiri ini laku sampai lebih dari 2 juta copy di Amerika Serikat. Single pertama "Where Have All the Cowboys Gone?" dikeluarin pada 25 Maret 1997 dan ada di urutan delapan Billboard Hot 100. Tujuh bulan kemudian lagu "I Don't Want to Wait" jadi single kedua. Peter Gabriel juga sumbang suara di lagu "Hush, Hush, Hush".
Album ini juga membuat Paula mendapat 7 nominasi Grammy Award 1997. Salah satunya "Producer of the Year" yang menjadikannya perempuan pertama yang mendapat nominasi itu. Dia membawa pulang gelar "Best New Artist". Paula sangat bahagia karena yang memberikan penghargaan itu adalah Aretha Franklin, idolanya sejak kecil.
Paula Cole masih terus bikin album namun tidak ada yang bisa menyaingi "This Fire". Selain nyanyi, Paula juga sibuk dalam berbagai kegiatan sosial dan lingkungan. Dia juga ngajar mata kuliah vokal di almamaternya sejak 2013 lalu.
