DeAnda was born in San Antonio, Texas to Mexican parents Steven and Barbara, a restaurant general manager and a registered nurse. At age six she began taking piano lessons and was soon singing at functions around town at the recommendation of her piano teacher. She also sang the national anthem at local football games. In 2002, DeAnda's family decided to move to Corpus Christi in order to help further her career in music because Corpus Christi had a reputation as a music hub. She attended Mary Carroll High School.
DeAnda was the opening act for a concert which featured hip-hop artists, Nelly, Baby Bash and Frankie J. performing in front of twenty thousand people. Her first single, "What Would It Take" was serviced to local radio stations in July, received airplay from ten radio stations across the country. The song was later switched for "Doing Too Much" in December when Ocana secured a mini-tour of California and Texas for DeAnda. The song became a minor hit in the Southwest. It was then that she got the opportunity to audition for Clive Davis who signed her for a seven-album deal with Arista Records on the spot. "Doing Too Much" was certified gold in the US in 2007. "Doing Too Much" missed the top 40 on the Billboard Hot 100, it served as the lead single to her self-titled debut album which was released in the summer of 2006. Paula DeAnda charted at number 54 on the US albums chart. The album mainly consists of songs about love and relationships and is of the pop-R&B genre. DeAnda co-wrote four songs on the album, which features production from Happy Perez among others. She was only 16 years old at the time of the album's released. Her second single "Walk Away (Remember Me)" was her biggest hit, reaching the top twenty on the Hot 100. The single was certified gold by the RIAA. However, follow-up singles, "When It Was Me" and "Easy" did not gain traction. She later acted in the MTV television film Super Sweet 16: The Movie. In 2008, DeAnda began production on next effort, initially due in 2009. A single, "Roll the Credits", was released and a video was planned, but it did not chart. Clive Davis left Arista's parent company at the time, RCA Label Group in 2008 to become the chief creative officer for Sony BMG. DeAnda also parted ways Arista following his departure.