Paul was born the eldest son of musical parents and grew up in Eugene, Oregon. His mother was a talented organist and classical accompanist in the family's church congregation; his father played piano and sang pop rock favorites, often serenading Paul and his brothers to sleep at night to the tunes of Billy Joel, Elton John, and Chicago.

Paul began classical piano training at a young age, practicing regularly on the family's prized black Kawaii baby grand piano (and occasionally on his father's Kurzweil digital piano). He also began singing at a young age—mostly in church and school choirs and performing at the occasional Christmas concert.

In middle school, Paul picked up the tenor sax and immediately fell in love with playing in a band. Through his years at Henry D. Sheldon High School, Paul participated in every band opportunity he could find including classical band, jazz band, pep band, pit orchestra, and marching band. One day during his sophomore year, Paul's band director, Gene Perry, showed up at his doorstep asking whether Paul would be willing to learn oboe for a song the band was playing that year. Paul happily obliged. A few years later, discovering that the sax was neither loud, light, nor water-proof, Paul taught himself the trumpet to perform with the marching band at football games his senior year. He meanwhile continued privately studying piano.

Paul's favorite musical moments were those that afforded opportunities to perform solo. In jazz band, he always took a turn at improvising. He did the same in pep band. Each year when the school put on its musical theater production, Paul was quick to volunteer. His favorite was when the school performed Grease Lightning. The show was basically one long tenor sax jazz improv solo, and Paul loved it.

It was during this time that Paul began receiving opportunities to do solo performances outside of band: play piano and sing at a Valentine's Day party or a school district teacher training. He played and sang songs from the books he had at at home: Billy Joel, Elton John, and Chicago. Paul's music success came to a pinnacle at the end of his senior year when he was honored with the the Louis Armstrong Award (the "top senior jazz award" or highest level interscholastic award given to students at high schools in the US) and the CAM Performing Arts award (the "top senior classical band award"). In a matter of a few weeks, Paul performed Billy Joel's Lullabye (Goodnight, My Angel) for an audience of several hundred people at the Mr. Irish Children's Miracle Network Pageant; We Didn't Start the Fire for several hundred more at the International High School graduation ceremony; and Baby Grand for several thousand people at Sheldon High School's graduation ceremony at Eugene's acclaimed Hult Center for the Performing Arts. A fire had been lit. Musical performance had become a passion.

In 2002, being overconfident in his academic abilities, Paul applied to a mere three universities: University of Oregon, Stanford University, and Brigham Young University in Provo, Utah. When he failed to get in to Stanford and decided he didn't want to go to the hometown school, he took the only choice he had left: BYU. Having been raised Mormon, Paul quickly found his place at BYU. Fearful that trying to make a career in music was not economically viable, Paul registered initially as a math major. He would declare a total of 8 majors over 6 years before finally graduating (Mathematics, Molecular Biology, Microbiology, Physiology and Developmental Biology, Animation, Computer Science, Italian, and Bioinformatics). He minored in Music.

His freshman year, Paul was awarded a scholarship to play trumpet in the BYU marching band and also successfuly auditioned to play saxophone in a jazz combo. When a roommate took the beginning songwriting class, Paul picked the friend's brain to learn everything he could. Over the course of that year, he wrote his first songs: My Favorite Stars, Still Not Over You, and Jessica.

Like many Mormon young men, Paul took a break after his first year of college and signed up to serve a two-year proselyting mission for the church. He was called to labor in the Italy Milan mission speaking Italian. At the Missionary Training Center, Paul discovered he had been assigned to a group of missionaries that all shared something in common: a love of singing and talent to go with it. Each night before retiring to bed, the 7 young men would gather and sing hymns in Italian, each singing a different part to create a rich, beautiful harmony. Paul's skills on the piano were also put to regular use as they would be throughout the duration of his time as a missionary. On Paul's second Christmas in Italy, he traveled the country on special assignment from the mission president, playing and singing his own custom arrangements of Christmas music for missionaries in every zone in the mission.

After completing his Bachelor's in 2010, Paul gave up just about everything to focus on graduate school, getting married, and starting a family. To keep active in music, he recruited several other Vocal Point alumni and together joined another lower-stakes BYU a cappella group, The Advocates, with which he performed and arranged music until 2012.

In 2014, Paul made the life-altering decision to formally embrace music as part of his career goal. Paul was terrified of taking a risk on his career, but relinquishing music had taken a severe toll on his mental health. Having earned a Bachelor's degree in Bioinformatics and a Master's degree in Computer Science, Paul decided to take a daunting leap into a subfield of Artifical Intelligence called Computational Creativity. In one of his early meetings with his would-be doctoral advisor, Dr. Dan Ventura, Paul shared his vision of wanting to research and design a system to compose its own lyrical pop-style music. It felt like a calling, something he had been perfectly positioned to do. In that first meeting Paul told Dr. Ventura in essence, ``I don't know if I'll be the best AI music researcher in the world, but what if I could be and never tried?'' Dr. Ventura said he was willing to give Paul a chance.

Wanting to stay close to family, Paul's took a tenure-track professor position in the Computer Science Department at Idaho State University in 2018. This newfound stability afforded Paul increased time and opportunity to invest in solo performing. Within a few years he was playing regularly for scholarship dinners with the Elks Lodge and solo gigging at Portneuf Valley Brewing, inviting friends, family, colleagues, and students to come enjoy an evening out. There soon formed a group of regular attendees donning t-shirts labeled "Bodily Bodies: The Paul Bodily Fan Club."

Within six months of solo performing, Paul was approached one evening by a bassist (Chris Porter) and a guitarist (Travis Erickson) interested in forming a band. They soon found a drummer (Clif Gobles) and within months Pop Rox had its debut show at First National Bar ("The Nash") in Pocatello. For Paul, who had long dreamed of being part of a professional rock band, this was a dream come true. They played a variety of 60's, 70's, and 80's pop rock hits, providing Paul the opportunity to build is repertoire and familiarity with a genre he already knew and loved. Besides regular performances at The Nash, the band played gigs at several other local venues including Star Route Brewery, The Stump, and The Rooftop Bar in Lava Hot Springs. Paul performed with Pop Rox until the band separated in Fall 2023.