Het album werd geschreven door de band in Byron Bay gedurende zes maanden waarna opnames plaatsvonden in Los Angeles gedurende maart/april van 2010. Deep Blue gaat over het zoeken naar waarheid in een wereld waar deze niet bestaat. Zanger en frontman Winston McCall zei dat "het verhaal door de ogen van een man wordt verteld die wakker wordt en zich realiseerd dat zijn leven een leugen is en alles waarin hij gelooft niet bestaat. Hij gaat dus de waarheid in hem zelf zoeken en deze reis brengt hem naar de bodem van de oceaan en terug".
Op 18 mei plaatste Parkway Drive het nummer "Sleepwalker" op hun MySpace profiel. In de video van "Sleepwalker", opgenomen in Brisbane, Australië, speelt Kevin Call van Comeback Kid een cameo rol. Op 16 juni plaatste ze het nummer "Unrest" op MySpace. Vlak daarna op 18 juni lekte het album uit op het internet en op 19 juni was het album in zijn geheel te beluisteren via sites als YouTube.