Sachverhalt: A. A.a A._ (Kläger, Beschwerdeführer) hat Wohnsitz in Italien. Seiner Ehefrau gehörte die Gesellschaft Hotel Z._ S.r.l., die zwei Hotels in Italien betrieb. 2002 wurden die Eheleute in einer über mehrere Wochen dauernden Inszenierung Opfer einer italienischen Betrügerbande. Anfang Mai 2002 wurde A._ angefragt, ob er erwäge, die seiner Ehefrau gehörende Gesellschaft zu verkaufen. In der Folge fanden mehrere Treffen an unterschiedlichen Orten in Italien und eine letzte Besprechung in I._ statt, an welchen A._ mit verschiedenen Personen bekannt gemacht wurde, die sich entweder als Vermittler oder als Vertreter einer potentiellen Käuferschaft ausgaben. A.b An einem Treffen am 28. Juni 2002 wurde A._ mit B._ bekannt gemacht, dem angeblichen Vertreter der Käuferschaft. Am 11. Juli 2002 einigte man sich in I._ darauf, einen Kaufvertrag über EUR 16 Millionen abzuschliessen, wobei EUR 2 Millionen in zwei Schritten bar an die Käuferschaft bzw. an die Vermittler zurückerstattet werden sollten. Die Unterzeichnung des Vorvertrags sollte am 18. Juli 2002 in einer Bank in J._ stattfinden. A._ sollte dort auch gleich ein Konto eröffnen, auf welches die erste Hälfte des Kaufpreises unmittelbar nach der Vertragsunterzeichnung und die zweite Hälfte nach Übertragung der Gesellschaft überwiesen werden sollte. A.c Zur Vorbereitung der Bargeldübergabe liess A._ am 1. Juli 2002 je EUR 500'000.-- auf ein Konto lautend auf seinen Namen und ein solches lautend auf den Namen seiner Ehefrau überweisen. Am 4. Juli 2002 liess er sich insgesamt EUR 1 Million bar auszahlen. Das Geld deponierte er in einem eigens dafür gemieteten Banksafe, für den er eine auf seine Assistentin lautende Vollmacht ausstellen liess. A.d Die Vertragsunterzeichnung wurde von der Käuferschaft kurzfristig auf den 22. Juli 2002 verschoben. An diesem Tag holte B._ die Eheleute A._ im Hotel ab und brachte sie zur Aussenstelle der Bank X._ (Beklagte, Beschwerdegegnerin). Die Räumlichkeiten befanden sich im zweiten Stock eines Bürogebäudes und waren Besuchern nur auf Einlass durch die Angestellten zugänglich. Vor dem Gebäude vergewisserte sich A._ telefonisch bei einem Bekannten, dass die Bank X._ seriös sei. A.e In den Räumlichkeiten der Bank X._ wurden die Eheleute A._ von zwei weiteren, ihnen bisher unbekannten Mitgliedern der Betrügerbande erwartet, C._ und D._. Diese hatten sich der Bank X._ gegenüber als potentielle Kundenvermittler ausgegeben und die Eheleute A._ sowie B._ bereits angekündigt. C._ empfing diese an der Türe und begrüsste B._ wie eine alte Bekanntschaft. Hinter der Theke befand sich E._, eine Angestellte der Bank X._. Bei den Eheleuten A._ entstand der Eindruck, C._ sei Angestellter, E._ eine untergeordnete Mitarbeiterin oder Sekretärin und B._ ein geschätzter Kunde der Bank X._. Die Eheleute A._ begaben sich daraufhin mit B._ und C._ in ein Besprechungszimmer. Dort kam D._ hinzu. Bei den Eheleuten A._ konnte der Eindruck erweckt werden, er sei der Niederlassungsleiter oder gar der Direktor der Bank X._. A.f Nach der Vertragsunterzeichnung wurde A._ aufgefordert, nun ein Konto bei der Bank X._ zu eröffnen. Zu diesem Zweck wurde E._ hereingebeten, welche mit den Eheleuten A._ die Formalitäten erledigte. Daraufhin verliess diese den Raum wieder. B._ eröffnete A._, er könne die Anzahlung wider Erwarten doch nicht sogleich überweisen. Er erhielt dabei Unterstützung von D._, der die Bonität von B._ versicherte. Da A._ verärgert reagierte, diskutierten D._ und B._ Möglichkeiten, die Summe kurzfristig aufzutreiben, und baten zu diesem Zweck um zwei Stunden Zeit. Die Eheleute A._ warteten in einem Restaurant. B._ wies ihnen in der Folge einen auf die Kontonummer von A._ lautenden, unterzeichneten Zahlungsauftrag über EUR 8 Millionen vor. Er bat die Eheleute in die Räumlichkeiten der Bank X._ zurück. Dort wurden sie von D._ in einem anderen Raum erwartet. In diesem befand sich auch E._. D._ erklärte, B._ habe einen unwiderruflichen Zahlungsauftrag unterzeichnet und unterstrich dessen Liquidität und Vertrauenswürdigkeit. Schliesslich rief A._ seine Assistentin in Italien an, um die Übergabe der EUR 1 Million in bar auszulösen. A.g Da auf seinem Konto keine Überweisung eingegangen war, verlangte A._ nach einigen Tagen, mit dem Filialleiter D._ zu sprechen. Als E._ ihm mitteilte, weder dieser noch C._ seien Angestellte der Bank X._, erkannte A._, dass er wohl einem Betrug zum Opfer gefallen war. C._ und weitere Mitglieder der Betrügerbande wurden in J._ wegen Betrugs verurteilt. Die übergebene Million Euro blieb unauffindbar. A._ macht nun gegen die Bank X._ einen Anspruch aus Vertrauenshaftung geltend. In der gegen sie eingeleiteten Betreibung über einen Betrag von Fr. 808'592.95 (EUR 500'000.--) erhob die Bank X._ Rechtsvorschlag. B. B.a Mit Klage vom 27. Mai 2008 beantragte A._ dem Zivilgericht Basel-Stadt, die Bank X._ sei zur Zahlung von EUR 500'000.-- bzw. Fr. 808'592.95 zu verurteilen und der Rechtsvorschlag in der entsprechenden Betreibung sei aufzuheben. Mit Entscheid vom 15. Oktober 2010 (Rektifikat vom 5. April 2011) wies das Zivilgericht die Klage ab. B.b Gegen diesen Entscheid erhob A._ beim Appellationsgericht des Kantons Basel-Stadt Berufung und wiederholte die erstinstanzlich gestellten Rechtsbegehren. Mit Entscheid vom 13. August 2012 wies das Appellationsgericht die Berufung ab. C. Mit Beschwerde in Zivilsachen vom 26. September 2012 beantragt A._ dem Bundesgericht, es sei das Urteil des Appellationsgerichts aufzuheben und die Beschwerdegegnerin zur Zahlung von EUR 500'000.-- bzw. Fr. 808'592.95 zu verurteilen. Die Beschwerdegegnerin beantragt die Abweisung der Beschwerde, soweit darauf einzutreten ist, eventuell die Rückweisung der Sache an die Vorinstanz. Die Vorinstanz beantragt die Abweisung der Beschwerde.