The song features a music video, however, Andrews doesn't appear in it. The video appeared on Billboard's "Hot Videoclip Tracks" chart in 2008. The video was directed by Christie Cook. A second version of the video with Bret Michaels in Iraq footage was released in 2008 when the song featured on the compilation Rock My World.
"All I Ever Needed" debuted at number 57 on the Hot Country Songs chart on October 9, 2004. The song spent 16 weeks on the country charts, even after the song reached its peak of number 45 in its fourth chart week. The song has also become Michaels' only chart entry on any Billboard chart to date.