Mit seinem Vater gemeinsam konnte er als Kind an den Musikaufnahmen zu einem Werbespot teilnehmen. In dem Song „Secret Lemonade Drinker“ ist seine Stimme im Hintergrund zu hören. Der Spot warb für eine Limonadenfirma. Seine erste sogenannte Bühnenerfahrung sammelte er als Jugendlicher im Kirchenchor. Doch schon 1971 freute er sich über seinen ersten bezahlten Auftritt. Jedoch handelte es sich hier nur um ein Trinkgeld von 50 Pence, das ihm beim St. Georges Project in Liverpool zugesteckt wurde. Er begann eine berufliche Laufbahn als Computer Operator, doch versäumte er keine Gelegenheit, sich als Musiker hervorzutun. Verschiedene kleinere Auftritte als Solosänger oder im Duett „Rusty“ mit Allan Mayes in Nachtclubs gaben ihm zusätzliche Erfahrungen auf der Bühne. Im Jahr 1975 konnte er dann mit seiner Band Flip City ein erstes Studioalbum aufnehmen. Zu dieser Zeit nannte er sich erstmals DP Costello. DP stand für Declan Patrick und Costello war der Mädchenname seiner Urgroßmutter väterlicherseits. Seine Urgroßeltern schienen für die musikalische Laufbahn der Familie eine große Bedeutung zu haben. Sein Großvater Patrick MacManus wuchs als Waise auf, nachdem seine Eltern bei unterschiedlichen Unfällen ums Leben kamen. Er lernte im Waisenhaus Musikinstrumente zu spielen und gab die Liebe zur Musik an seinen Sohn Ross und dessen Kinder weiter. Patricks Mutter war mit dem Namen Costello geboren, den der Enkel Declan Patrick später als Künstlername annahm. Auf Anraten seines Managers änderte er später seinen Vornamen in Elvis. Dies sollte eine Anspielung auf den König des Rock and Roll Elvis Presley sein. Äußerlich versuchte Elvis Costello ein wenig dem ebenso bekannten Buddy Holly nachzueifern. Die große Brille und die Frisur ergaben eine gewisse Ähnlichkeit zwischen den beiden.
Die Plattenfirma plante für Flip-City sogar eine Single-Auskopplung des Songs Third Rate Romance. Leider erreichte eine andere Version des Liedes (gesungen von Jesse Winchester) zu dieser Zeit wahren Kultcharakter bei dem Sender BBC. Um nicht auf dieser Welle reiten zu müssen, wurde der Plan verworfen. Schon 1976 hatte Flip City seinen letzten Auftritt. Gleichzeitig wagte DP Costello seine ersten großen Solo-Auftritte. Er konnte einige selbst aufgenommene Titel wie “Wave A White Flag”, “Jump Up”, “Poison Moon” and “Mystery Dance” an die BBC überspielen. Im Rahmen der Show „Honky Tonk“ wurden diese Titel auch gesendet.
Kurz darauf überbrachte er ein erstes Demo-Band an das neu gegründete Label Stiff Records. Zuerst wurde er hier vor allem als Songwriter gesehen. Die ersten Aufnahmen stellten bloß Demos für andere Künstler dar. Es war durchaus üblich, dass selbst geschriebene Musikstücke von den Songwritern zunächst zu Hause vertont wurden, um sie später dem Plattenlabel und dem Künstler vorzuspielen. Ein Songwriter musste also stets auch selbst eine gute Stimme haben, um seine Songs verkaufen zu können. Costello akzeptierte auch den kleinen Erfolg als Songwriter und nicht als Sänger. Dennoch konnte er mit der Begleitband Clover schon 1977 sein erstes Album veröffentlichen. “My Aim Is True” schaffte es bereits in die Top 40 der Billboard Charts. Bis dahin vergingen allerdings einige Monate, in denen er weiterhin als Computer Operator arbeiten musste. In der Plattenfirma schien sein Talent als Sänger zunächst nicht erkannt zu werden.