The theme song became a popular hit during the run of The Greatest American Hero. "Believe It or Not" debuted in the Top 40 of the Billboard Hot 100 on June 13, 1981, eventually peaking at number 2 during the weeks ending August 15–22, 1981, kept off the top spot by "Endless Love" by Diana Ross and Lionel Richie, and spending a total of 18 weeks in the Top 40. On the Adult Contemporary Chart, "Believe It or Not" went to number 3. It also peaked at the number 1 position on the Record World chart. It was also used in the 2009 movie Super Capers.
George uses a modified version of this song for his answering machine greeting in the Seinfeld episode The Susie. The following is sung by George to the tune of the refrain: "Believe it or not, George isn't at home, please leave a message at the beep. I must be out, or I'd pick up the phone, where could I be? Believe it or not, I'm not home."