All Time Low sa sformovali v roku 2003, kedy ešte stále boli na strednej škole a začali prespievavať pesničky od pop punkových kapiel ako sú napríklad Blink-182. Neskôr nahrali svoj prvý album s Emerald Moon Records, s ktorými podpísali zmluvu v roku 2004 a vzápätí vydali svoje prvé EP album The Three Words to Remember in Dealing with the End. Kapela neskôr vydala prvý oficiálny album The Party Scene a to v júli 2005.