Il singolo di Mr Brightside era stato pubblicato la prima volta solo in UK il 29 Settembre 2003, in versione cd singolo e vinile 7″, entrambi limitati a 500 copie. Come lato B del cd singolo ci sono due canzoni che faranno poi parte di Hot Fuss (On Top e Smile Like You Mean It).
Dopo il successo ottenuto con Somebody Told Me il singolo è stato ripubblicato nel Maggio del 2004 con una copertina diversa. Nel resto d’Europa l’uscita è stata di circa un anno di ritardo rispetto al Regno Unito.

Mr Brightside è sicuramente il singolo più conosciuto dei Killers, nonché la prima canzone scritta da Brandon e Dave ancor prima che la band si formasse. Già al primo incontro fra i due, infatti, Dave dà a Brandon una cassetta con incise quattro canzoni e alcuni riff di chitarra. “Su quella cassetta c’era la linea di chitarra di Mr Brightside – una piccola parte del verso e del pre-coro, anche se era solo un abbozzo in quel momento — ed era il pezzo che mi ha colpito subito. Allora ci siamo trovati e lui l’ha suonata, io ci ho cantato sopra e le parole solo venute fuori molto velocemente. Ci ho messo un coro alla fine e un pre-coro ed era pronta. Non avevamo la minima idea di quanto fosse buona come canzone. Si capiva che andava bene ma non avevamo un batterista e una canzone come Mr Brightside senza batteria rimane incompiuta. Con la band al completo diventa una gran bella canzone,” dice Brandon.
Il testo tratta di un ragazzo geloso che immagina come la sua fidanzata lo stia tradendo con un altro. Questo tema è molto autobiografico e Brandon ammette “sono un partner, fidanzato, marito veramente molto geloso. Sono conosciuto per questo e si riflette molto nelle canzoni. È facile scrivere delle cose che ti succedono in prima persona, quindi una canzone come Mr Brightside viene naturale. Io sono Mr Brightside. L’ho scritta quando stavo male dopo una brutta esperienza. Prendi quei momenti bui e li trasformi in canzoni.”

I video della canzone, seguendo le diverse tempistiche di uscite del singolo nel mondo, sono due. La prima versione, quella definita UK e diretta da Brad e Brian Palmer, è molto semplice: bianco e nero, la band che suona. La seconda versione, quella destinata al mercato internazionale e diretta da Sophie Mueller, prende come spunto il film Moulin Rouge. I due protagonisti del video, oltre alla band, sono interpretati da Eric Roberts, fratello della più famosa Julia, e dall’attrice polacca Izabella Miko (già protagonista de Le ragazze del Coyote Ugly). La città che si vede sullo sfondo della balconata in alcune scene è Firenze, mentre sulla batteria si legge ‘Genius Sex Poets’, una delle alternative con cui i Killers hanno pensato di chiamarsi prima di scegliere il loro nome attuale.