The song received positive reviews from most music critics. Stephen Thomas Erlewine from Allmusic called it "a breezy track". Sal Cinquemani from Slant says that "Paris's debut single, "Stars Are Blind" (which was commissioned to bridge the gap between the hip-hop and rock-inflected tunes on the album), has been the surprise of the summer, Nelly Furtado's "Promiscuous" notwithstanding; it's a sunny, reggae-hued love song that has eclipsed new singles by some of music's biggest stars. Leah Greenblatt from Entertainment Weekly called it: "a summery island groove". Alexis Petridis from The Guardian said that: "On Stars Are Blind, the combination of tinny cod-reggae and your-call-is-being-held-in-a-queue vocal technique results in something so plasticky, it's perversely enjoyable". Mark Daniels from Yahoo! Music said: "Even the plinky pop-reggae, never a good look, of single "Stars Are Blind" manages to ingratiate itself eventually".
"Stars Are Blind" was one of the highest debuting singles in the U.S. in 2006, entering the Billboard Hot 100 at number eighteen due to strong digital sales. It had previously debuted at number two on the U.S. Bubbling Under Billboard Hot 100 Chart (equivalent to #102 on the US Billboard Top 100).
Hilton shot the video for the single on Paradise Cove Beach in Malibu, California on May 24, 2006 directed by Chris Applebaum. The video for the song features many images of her walking and rolling around on the beach with a lover. It premiered on June 6, 2006 on MTV.
A second version of the video was shot for the European and Latin American countries, featuring Hilton's lover (played by Lucas Babin) from the beach as her photographer at a photoshoot. In this version, scenes from the beach are still present, but exist as Hilton's fantasies during the photoshoot. At the end of the video, she wins the affection of her photographer, but ends up just taking his keys and stealing his car. The second version premiered on Z100's website on July 5, 2006. The video is often called "Version 2" or "Black & White Version" or the "Clean version". This is the version that was accepted by other countries internationally rather than the first one.
In June 2007 the copyright holders of the 1970 song "Kingston Town", Sparta Florida Music Group, started legal action against Hilton and Warner Chappell Music for plagiarism due to alleged similarities between "Stars Are Blind" and "Kingston Town". The two songs use the same chord progression in the verses. It has wrongly been ascribed that UB40 was the suing party, but that has been denied by the band themselves on their website.