After a brief debate, the GOP-controlled Senate by a 27-4 vote sent the nominee of fellow Republican Perry back to the Nominations Committee, where it is expected to die.
While Perkins' lack of qualifications were cited as a reason for the surprise move, several senators said Perkins' involvement in a 2004 controversy over the sale of sex toys in her hometown of Burleson was a factor.
Just last week Perkins had been approved by the Nominations Committee, with a single dissenting vote.
Wednesday's public vote against a gubernatorial nominee is a rarity, something several senators said had not occurred in years. In most cases when senators want to derail a nomination, they block it so it never gets out of the committee.
At her Senate confirmation hearing last week, Perkins denied she had anything much to do with it.
Sen. John Whitmire, D-Houston, argued that Perkins was simply unqualified for the $95,000-a-year, full-time post.
"This is not a partisan issue. This is not a personal issue ... This is a life-and-death position. It demands qualifications.," Whitmire said.
Three other nominees to the parole board that were confirmed by the Senate are highly qualified, Whitmire said. Two are longtime board members who are being reappointed, and the other is a Huntsville attorney.
"They have multiple degrees ... (Perkins) has no college degree," he said, noting that Perkins has no criminal justice experience, other than working for a time as a prison ministry volunteer.
Sen. John Carona, R-Dallas, agreed. "The basis question is: Are there more qualified people out there?" he said.
As for the lingering issues, Whitmire said he was opposed to the nomination based solely on Perkins' lack of qualifications. "There are others that could be raised. I wish not to go there," he said.
After 10 minutes of debate, senators returned to their chairs and quietly voted down Perkins, in a chamber that is usually noisy with conversations.