Maybe Prophecy was the first official single, but I remember Nostradamus being the first song released period, even if it was only online. Kind of like how for the last AIC album, A Looking In View was the first song people heard but the first official single was Check my Brain.
04/01 - Mindless Self Indulgence
04/05 - Kataklysm
05/10 - Mastodon/Gojira
05/12 - Down