2007–08: The Memphis Album i Tour thumb|left|Sebastian z zespołem podczas trasy koncertowej w 2007 roku Na początku 2007 roku Sebastian poinformował, że rozpoczął pracę nad materiałem na nowy album, na którym znajdą się najpopularniejsze piosenki soulowe. Sesje nagraniowe płyty zostały zorganizowane w Memphis, piosenkarz zaprosił do udziału w nagraniach muzyków z wytwórni Stax, a także takich artystów, jak m.in. Steve Cropper, Steve Potts (znany także jako The MGs) czy Lester Snell. Płyta zatytułowana The Memphis Album miała swoją premierę w listopadzie tegoż roku, zadebiutowała na trzecim miejscu krajowych list najczęściej kupowanych albumów oraz została siódmym najczęściej kupowanym krążkiem australijskiego artysty w tym roku. Krążek uzyskał status podwójnej platynowej płyty w kraju.
Niedługo po powrocie Sebastiana do Australii artysta potwierdził, że na początku 2008 roku wyrusza w trasę koncertową po kraju razem z The MGs. Jeden z koncertów w Melbourne został nagrany oraz ukazał się w formie płyty koncertowej zatytułowanej The Memphis Tour. Wydawnictwo otrzymał nagrodę Helpmann Award za Najlepszy występ podczas współczesnego koncertu w Australii.