Born in Carbondale, Illinois, into a middle class family, Paul started playing guitar at the age of 5, but soon gave up, becoming frustrated with just learning simple nursery rhymes. Around age 11, he took up the guitar again, but with a skewed memory of the technique. Paul revealed at an Ibanez sponsored guitar clinic August 12, 2005 in Concord, CA at Spitzer's Music, that he "played only with upstrokes, used only the low 'E' string and only used [his] middle finger on the fretboard." Frustrated after trying to play the intro to "Barracuda" by Heart, he took lessons and his teacher explained the error of his ways. His technique corrected, Gilbert continued practicing and by the age of 14 he developed a local band in Greensburg, PA named Missing Lynx. They played together for approximately two years and wrote their own material. After Missing Lynx he then went on to join another local band called Tau Zero, but left shortly after, and headed for California. He was spotlighted in Guitar Player Magazine alongside fellow up-and-comer Yngwie Malmsteen.