Unbelievable est enregistrée entre février et mars 1990 du côté de Los Angeles pour l'album Under The Red Sky. Le refrain de la chanson fait penser à une comptine enfantine du genre "Une fourmi avec un chapeau sur la tête, ça n'existe pas, ça n'existe pas...".
Comme dans une comptine la rythmique de la ritournelle est entraînante et son sujet peut paraître un peu absurde. La chanson est sortie sous forme de single avec 10 000 men en B-Side. Elle a été jouée 29 fois depuis sa sortie. Dans le clip d'Unbelievable (réalisé en Juin 1990) Bob Dylan promène un porc, joue de la guitare et conduit une limousine pendant qu'un bellâtre a quelques petits problèmes.