Im Jahr 1977 castete Costello seine neue Band zusammen. Steve Nason, später unter dem Namen Steve Nieve bekannt, wurde für das Keyboard und Bruce Thomas als Bassist engagiert. Zusammen mit dem Trommler Pete Thomas, der jedoch mit Bruce nicht verwandt ist, bildeten sie „Elvis Costello and the Attractions“. Das Album “My Aim Is True” wurde neu aufgelegt und die Alben “This Year’s Model” und “Armed Forces” folgten in den Jahren 1978 und 79. Mit der neuen Band konnte er seinen Erfolg sogar auf den US-Markt ausdehnen. Mehrere Konzerttouren in ganz Europa und den USA wurden zu einem großen Erfolg.
1979 erfolgte jedoch bereits der erste Skandal, der die Karriere von Elvis Costello beinahe beendet hätte. In einer Kneipe in Florida entbrannte ein Wortgefecht, währenddessen er sich abfällig über afroamerikanische Musiker ausließ. Obwohl er sich öffentlich entschuldigte und bereits 1978 bei „Rock Against Racism“ aufgetreten war, nahmen viele amerikanische Hörer ihm die Bemerkung übel. Er musste seine Tour in den USA absagen. Auch die Verkaufszahlen der Alben brachen anschließend stark ein. Obwohl die Bemerkung, die ihm angelastet wurde, nur vollkommen aus dem Zusammenhang gerissen eine rassistische Färbung innehatte, konnte Costello den unbedachten Spruch so schnell nicht wieder zurücknehmen. Erst im Jahr 1981 sollte er das Land wieder betreten. Der europäische Erfolg scheint jedoch ungebrochen. Seine Veröffentlichungen im Jahr 1980 erreichen Plätze in den Top Ten der UK-Charts. Auch ein Auftritt in Neuseeland wurde zu einem großen Erfolg. Insgesamt veröffentlichten „Elvis Costello And The Attractions“ 9 Alben. Das Album „Blood and Chocolate“ aus dem Jahre 1986 sollte vorerst das letzte Werk in dieser Zusammenstellung sein, bevor 1996 mit „All this useless Beauty“ ein Revival gewagt wurde. Auf dem Album „Blood and Chocolate“ ist der Song „Tokyo Storm Warning“ mit Platz 73 in den britischen Singlecharts tatsächlich der erfolgreichste. Zwei weitere Songs schafften es auf die Plätze 79 und 94. Damit gehört dieses letzte Album zu den erfolglosesten Werken der Attractions.