Elvis Costello saapui paikalle ivallisena sylkykuppina, 1970-luvun brittiläisen punkin ensimmäisen aallon älykkäimpänä ja ilkeimpänä laulaja-lauluntekijänä, jonka tukena oli Attractions -yhtye, joka pystyi vastaamaan hänen raivoisuuteensa. Pian Costello laukkasi pois punkin äänekkäiden nopeiden sääntöjen tieltä ja osoitti musiikilliset ja verbaaliset kykynsä Armed Forces -albumilla vuonna 1979, joka sisälsi ”Oliver’s Army”, ”Accidents Will Happen” ja coverin Nick Lowen ”(What’s So Funny About) Peace, Love and Understanding” -nimisestä kappaleesta, jotka muuttuivat uuden aallon standardeiksi. Tällaisesta nopeasta musiikillisesta kehityksestä ja tyylinvaihdoksista tuli sääntö Costellon uralla, sillä hän keräsi luettelon, joka näytti koskettavan kaikkia mahdollisia populaarimusiikin tyylilajeja. Monet hänen esoteerisemmista projekteistaan tulivat keski-iässä ja sen jälkeen, kun hän oli 80-luvulla hankkinut itselleen uskollisen yleisön nopeatempoisilla mestariteoksilla, joista useimmat olivat Attractionsin tukemia. Myöhemmin hän kutsui bändin uudelleen koolle – ja vielä myöhemmin hän säilytti suurimman osan soittajista myöhempien aikojen taustaryhmässään Impostersissa – mutta vuoden 1989 Spike-levystä alkaen Costello tarttui sooloilun mukanaan tuomiin vapaamuotoisiin mahdollisuuksiin, jotka tulivat hänen soolona ollessaan, ja vaihteli tiheästä popista klassisiin sävellyksiin ja yhteistyöhön 60-luvun ikonien Paul McCartneyn ja Burt Bacharachin kanssa. Tämä seikkailunhalu lisääntyi 2000-luvulla, kun hän kiersi Impostersin kanssa, leikkasi americana-albumeita vanhan kohorttinsa T-Bone Burnettin kanssa ja teki yhteistyötä sekä New Orleansin R&B-legenda Allen Toussaintin että arvostetun hiphop-ryhmä The Rootsin kanssa. Hänen eklektisyytensä ei koskaan vaikuttanut pakotetulta: ainoa vakio hänen urallaan oli kyltymätön musiikin nälkä.
Brittiläisen bändinjohtaja Ross McManuksen poika Costello (syntyjään Declan McManus) työskenteli 70-luvun alkupuolella tietokoneohjelmoijana ja esiintyi D.P. Costello -nimellä erilaisilla folk-klubeilla. Vuonna 1976 hänestä tuli country-rock-yhtye Flip Cityn johtaja. Tänä aikana hän äänitti useita demonauhoja alkuperäistä materiaaliaan tarkoituksenaan saada levytyssopimus. Kopio näistä nauhoista päätyi Jake Rivieralle, yhdelle aloittelevan riippumattoman levy-yhtiön Stiffin johtajista. Riviera teki Costellon kanssa sopimuksen Stiffin kanssa sooloartistina vuonna 1977; laulaja/lauluntekijä otti tuolloin käyttöön nimen Elvis Costello ottaen etunimensä Elvis Presleystä ja sukunimensä äitinsä tyttönimestä.
Entisen Brinsley Schwarz -basistin Nick Lowen tuottaessa Costello aloitti debyyttialbuminsa äänitykset amerikkalaisen Clover-yhtyeen tukemana. ”Less Than Zero”, ensimmäinen näistä sessioista julkaistu single, ilmestyi huhtikuussa 1977. Single ei onnistunut kartoittaa, kuten ei sen seuraaja, ”Alison”, joka julkaistiin seuraavassa kuussa. Kesään 1977 mennessä Costellon pysyvä taustayhtye oli koottu. Ryhmään kuuluivat basisti Bruce Thomas, kosketinsoittaja Steve Nieve ja rumpali Pete Thomas (ei sukua Brucelle), ja se sai nimekseen Attractions; se debytoi livenä heinäkuussa 1977.
Costellon debyyttialbumi My Aim Is True julkaistiin kesällä 1977 positiivisten arvostelujen saattelemana; se nousi Britannian listoilla sijalle 14, mutta se julkaistiin hänen amerikkalaisella levy-yhtiölleen, Columbialle, vasta myöhemmin tänä vuonna. Yhdessä Nick Lowen, Ian Duryn ja Wreckless Ericin kanssa Costello osallistui Stiff-levymerkin Live package -kiertueelle syksyllä. Vuoden lopulla Jake Riviera erosi Stiffistä ja perusti Radar Recordsin, jolloin Costello ja Lowe lähtivät mukaan. Costellon viimeisestä sinkusta Stiffille, reggae-vaikutteisesta ”Watching the Detectives”, tuli Costellon ensimmäinen hitti, joka nousi vuoden lopulla sijalle 15.
This Year’s Model, Costellon ensimmäinen Attractionsin kanssa äänitetty albumi, julkaistiin keväällä 1978. My Aim Is True -levyä raaempi ja kovempaa rockia sisältävä levy This Year’s Model oli myös suurempi hitti, sillä se nousi Britanniassa sijalle neljä ja Amerikassa sijalle 30. Seuraavana vuonna julkaistu Armed Forces oli kunnianhimoisempi ja musiikillisesti monipuolisempi albumi kuin kumpikaan hänen edellisistä levyistään. Se oli toinen hitti, joka ylsi Britanniassa kakkoseksi ja Yhdysvalloissa kymmenen parhaan joukkoon. ”Oliver’s Army”, albumin ensimmäinen single, ylsi myös Britanniassa kakkoseksi; yksikään Armed Forcesin singleistä ei noussut listoille Amerikassa. Kesällä 1979 hän tuotti ska-herätysliikkeen johtajan The Specialsin samannimisen debyyttialbumin.
Helmikuussa 1980 julkaistiin soul-vaikutteinen Get Happy!!!; se oli Rivieran uuden levy-yhtiön, F-Beatin, ensimmäinen levy. Get Happy!!! oli toinen hitti, joka nousi Britanniassa sijalle kaksi ja Amerikassa sijalle 11. Myöhemmin samana vuonna Amerikassa julkaistiin kokoelma B-puolia, singlejä ja outtakeja nimeltä Taking Liberties; Britanniassa samanlainen albumi nimeltä Ten Bloody Marys & Ten How’s Your Fathers ilmestyi vain kasettijulkaisuna, jossa oli eri kappaleet kuin amerikkalaisessa versiossa.
Costello and the Attractions julkaisi Trustin alkuvuodesta 1981; se oli Costellon viides Lowen tuottama albumi peräkkäin. Trust debytoi Britannian listoilla sijalla yhdeksän ja raivasi tiensä Top 30:een Yhdysvalloissa. Kevään 1981 aikana Costello ja Attractions alkoivat nauhoittaa country-covereita sisältävää albumia kuuluisan Nashvillen tuottajan Billy Sherrillin kanssa, joka oli levyttänyt hittilevyjä muun muassa George Jonesille ja Charlie Richille. Tuloksena syntynyt albumi, Almost Blue, julkaistiin vuoden lopulla ja sai ristiriitaisia arvioita, vaikka single ”A Good Year for the Roses” olikin Britannian Top Ten -hitti.
Costellon seuraava albumi Imperial Bedroom (1982) oli kunnianhimoinen sarja rehevästi sovitettua poppia, jonka tuotti Geoff Emerick, joka oli tuottanut useita Beatlesin ylistetyimpiä albumeita. Imperial Bedroom sai joitakin hänen parhaista arvosteluistaan, mutta se ei kuitenkaan tuottanut Top 40 -hittiä Englannissa eikä Amerikassa; albumi debytoi kuudennella sijalla Isossa-Britanniassa. 1983 julkaistulla Punch the Clock -albumilla Costello työskenteli Clive Langerin ja Alan Winstanleyn kanssa, jotka olivat vastuussa useista suurimmista brittiläisistä hiteistä 80-luvun alussa. Yhteistyö osoittautui kaupallisesti menestyksekkääksi, sillä albumi oli korkeimmillaan kolmossijalla Isossa-Britanniassa (sijalla 24 Yhdysvalloissa) ja single ”Everyday I Write the Book” nousi 40 parhaan joukkoon sekä Isossa-Britanniassa että Amerikassa. Costello yritti toistaa Punch the Clockin menestyksen seuraavalla levyllään, vuoden 1984 Goodbye Cruel Worldilla, mutta albumi oli kaupallinen ja kriittinen epäonnistuminen.
Goodbye Cruel Worldin julkaisun jälkeen Costello lähti ensimmäiselle soolokiertueelleen kesällä 1984. Vuonna 1985 hän oli suhteellisen passiivinen, hän julkaisi vain yhden uuden singlen (”The People’s Limousine”, yhteistyö laulaja/lauluntekijä T-Bone Burnettin kanssa, joka julkaistiin nimellä The Coward Brothers) ja tuotti Rum Sodomy and the Lash, punk-folk-yhtye The Poguesin toisen albumin. Molemmat projektit olivat merkkejä siitä, että hän oli siirtymässä kohti pelkistettyä, folkahtavaa lähestymistapaa, ja vuoden 1986 King of America vahvisti tämän epäilyn. Ilman Attractionsia äänitetty ja Costello Show -nimellä julkaistu King of America oli pohjimmiltaan country-folk-albumi, ja se sai parhaat arvostelut kaikista hänen Imperial Bedroomin jälkeen äänittämistään albumeista. Sitä seurasi vuoden lopulla särmikäs Blood and Chocolate, joka oli jälleennäkeminen Attractionsin ja tuottaja Nick Lowen kanssa. Costello levytti toisen albumin Attractionsin kanssa vasta vuonna 1994.
Vuoden 1987 aikana Costello neuvotteli uuden maailmanlaajuisen levytyssopimuksen Warner Bros:n kanssa ja aloitti lauluntekijäyhteistyön Paul McCartneyn kanssa. Kaksi vuotta myöhemmin hän julkaisi Spiken, musiikillisesti monipuolisimman kokoelman, jonka hän oli koskaan levyttänyt. Spike sisälsi ensimmäistä kertaa Costellon ja McCartneyn kirjoittamia kappaleita, muun muassa singlen ”Veronica”. ”Veronica” nousi hänen suurimmaksi amerikkalaiseksi hitikseen ja oli korkeimmillaan sijalla 19. Kaksi vuotta myöhemmin hän julkaisi Mighty Like a Rose -levyn, joka toisti Spikea monipuolisuudessaan, mutta oli kuitenkin synkempi ja haastavampi levy. Vuonna 1993 Costello teki yhteistyötä Brodsky Quartetin kanssa The Juliet Letters -laulusyklissä, joka oli lauluntekijän ensimmäinen yritys klassisen musiikin parissa; hän kirjoitti myös kokonaisen albumin entiselle Transvision Vamp -laulajalle Wendy Jamesille nimeltä Now Ain’t the Time for Your Tears. Samana vuonna Costello lisensoi oikeudet vuotta 1987 edeltävään katalogiinsa (My Aim Is True to Blood and Chocolate) amerikkalaiselle Rykodiscille.
Costello yhdistyi uudelleen Attractionsin kanssa nauhoittaakseen suurimman osan vuoden 1994 Brutal Youth -albumista, joka oli suoraviivaisin ja pop-painotteisin albumi, jonka hän oli levyttänyt sitten Goodbye Cruel Worldin. Attractions tuki Costelloa maailmanlaajuisella kiertueella vuonna 1994 ja konsertoi hänen kanssaan koko vuoden 1995. Vuonna 1995 hän julkaisi pitkään hyllyssä olleen cover-kokoelmansa Kojak Variety. Keväällä 1996 Costello julkaisi All This Useless Beauty -kokoelman, joka sisälsi useita alkuperäisiä kappaleita, joita hän oli antanut muille artisteille mutta ei koskaan levyttänyt itse. Painted from Memory, yhteistyö legendaarisen Burt Bacharachin kanssa, seurasi vuonna 1998. Albumi oli kriittinen menestys, mutta se menestyi vain ulkomaisilla markkinoilla, kotimaidensa Yhdysvaltojen ja Britannian ulkopuolella. Bill Frisellin kanssa tehty jazz-versio levystä pantiin jäihin, kun Costellon levy-yhtiö alkoi jäätyä poliittisten manööverien takia. Lannistumatta Costello ja Bacharach lähtivät tien päälle ja esiintyivät Yhdysvalloissa ja Euroopassa. Bacharachin lähdettyä Costello lisäsi kiertueeseen Steve Nieven, ja he kiersivät maailmaa Lonely World Touriksi kutsutulla kiertueella. Tämä vei heidät vuoteen 1999, jolloin sekä Notting Hill että Austin Powers: The Spy Who Shagged Me -elokuvissa Costello osallistui merkittävästi. Itse asiassa hän esiintyi Bacharachin kanssa jälkimmäisessä elokuvassa yhtenä Carnaby Streetin muusikkoparista, vaikkakin katumuusikkoina, joilla oli käytössään upea flyygeli.
Jatkaen kiertuettaan Nieven kanssa, hän alkoi laulaa viimeistä kappaletta ilman mikrofonia, pakottaen yleisön istumaan täydellisessä hiljaisuudessa, kun hän yleensä esitti ”Couldn’t Call It Unexpected, No. 4” ilman mitään muuta kuin hänen herttaisen baritoninsa täyttämään salin. Levy-yhtiön erilaisten fuusioiden päätyttyä Costello löysi itsensä Universalilta ja testasi heidän myynninedistämiskykyään toisella greatest-hits-levyllä (The Very Best of Elvis Costello). Levy-yhtiö mainosti levyä voimakkaasti, mikä teki siitä hitin hänen kotimaassaan Britanniassa. Valitettavasti he myös tekivät selväksi, että heillä ei ollut aikomustakaan antaa uudelle albumille samanlaista mainostusta, joten Costello joutui levytyssopimuksensa päättymistä odotellessaan kokeilemaan muita aloja. Hänen ensimmäinen projektinsa oli Anne Sofie Von Otterin kanssa esitetty kokoelma pop-standardeja, joka sisälsi muutamia Costellon alun perin kirjoittamia kappaleita. Albumi julkaistiin maaliskuussa 2001 Deutsche Grammophon -levymerkillä, ja se osui sopivasti samaan aikaan, kun hänen koko kataloginsa vuoteen 1996 asti julkaistiin uudelleen Rhino Recordsin kautta. Kumpaankin levyyn sisältyi ylimääräinen CD-levy harvinaista materiaalia ja Costellon itsensä kirjoittamat muistiinpanot, mikä tekee niistä uskomattomia herkkuja faneille.
Vuonna 2001 hän löysi itsensä UCLA:n residenssistä, jossa hän esiintyi useissa konserteissa ja oli vuoden aikana mukana musiikin opetuksessa. Hän aloitti myös työn itse tuotetun albumin parissa, jossa esiintyivät Pete Thomas ja Nieve – nyt Imposters-nimisenä yhtyeenä – nimeltään When I Was Cruel, ja albumi löysi vihdoin julkaisun Island Recordsilla keväällä 2002; vuoden lopulla hän julkaisi kokoelman B-puolia ja tähteitä albumin sessioista nimeltään Cruel Smile.
When I Was Cruel aloitti uuden tuottoisan aikakauden alati tuotteliaalle Costellolle. Vuonna 2003 hän palasi Northilla, kokoelmalla klassisen tyylisiä pop-kappaleita, jotka sijoittuivat Gershwinin ja Sondheimin välimaastoon. Seuraavana vuonna hän teki yhteistyötä uuden vaimonsa Diana Krallin kanssa tämän ensimmäisellä alkuperäismateriaalikokoelmalla The Girl in the Other Room. Samana syksynä Costello julkaisi kaksi albumia omaa alkuperäismateriaalia: klassisen teoksen nimeltä Il Sogno ja konseptilevy The Delivery Man, Impostersin kanssa leikattu rock & roll -levy. Vuonna 2006 julkaistu My Flame Burns Blue oli livealbumi, jolla Costello johti 52-henkistä jazz-orkesteria Metropole Orkestia; julkaisu sisälsi klassisia Costellon kappaleita (uusilla orkesterisovituksilla) uusien sävellysten ja Il Sognon esityksen ohella kokonaisuudessaan.
The River in Reverse, yhteistyö R&B-legenda Allen Toussaintin kanssa, saapui vuonna 2006, ja sitä seurasi Momofuku, toinen Elvis Costello & the Imposters -yhtyeen kreditoima ponnistus, vuonna 2008. Samana vuonna Costello lyöttäytyi yhteen veteraanituottaja T-Bone Burnettin kanssa useisiin äänityssessioihin, joiden tulokset koottiin Secret, Profane & Sugar Cane -levyksi ja valmisteltiin julkaistavaksi vuoden 2009 alussa. Kaksikko äänitti myös toisen albumin, National Ransom, joka ilmestyi seuraavana vuonna. Vuonna 2011 Costello & the Imposters julkaisi The Return of the Spectacular Spinning Songbook!!! -levyn, joka nauhoitettiin livenä kahden päivän aikana Wilternissä Los Angelesissa. Noin seuraava vuosi oli suhteellisen hiljainen, mutta vuoden 2012 lopussa hän julkaisi uuden kokoelman nimeltä In Motion Pictures, joka kokosi hänen elokuviin vaikuttamiaan kappaleita.
Costello omistautui vuonna 2013 työskentelylle hiphop-yhtye The Rootsin kanssa. Alun perin hänen laajan kataloginsa kappaleiden uudelleentulkinnaksi suunniteltu Wise Up Ghost -albumi muuttui täysimittaiseksi yhteistyöksi, ja se sai myönteisiä arvioita, kun se julkaistiin syyskuussa 2013 Blue Notella. Vuonna 2015 Costello ilmoitti viimeistelevänsä muistelmateoksensa, ja kirjan, jonka nimi on Unfaithful Music & Disappearing Ink, oli määrä ilmestyä lokakuussa 2015. Costello kokosi myös oheisalbumin, Unfaithful Music & Soundtrack Album, joka sisälsi uran kattavan valikoiman kappaleita hänen katalogistaan sekä kaksi aiemmin julkaisematonta valintaa.
Heinäkuussa 2018 Costello paljasti toipuvansa ”pienestä mutta hyvin aggressiivisesta syövästä”. Kun hän kertoi uutisen, hän ei ollut vain toipumassa, vaan hänellä oli myös uusi albumi Impostersin kanssa tekeillä. Look Now, ryhmän ensimmäinen yhteinen levy vuosikymmeneen, ilmestyi lokakuussa 2018; se voitti Grammy-palkinnon parhaasta perinteisestä poplaulualbumista seuraavana vuonna. Look Nowa seurasi nopeasti vuonna 2020 Hey Clockface, ensimmäinen Elvis Costellon sooloalbumi kymmeneen vuoteen.