Sachverhalt:
A. X._ wird vorgeworfen, ab Oktober 1995 bis August 1998 mehrere Geldbeträge von Y._ erhalten zu haben, um diese in der Schweiz anzulegen. Er habe die Barbeträge mehrheitlich auf ein dazu eigens (im Jahre 1995) eröffnetes Konto bei der früheren Bank A._ AG einbezahlt. Dieses Konto habe er im September 1997 eigenmächtig saldieren lassen und die Überweisung der Vermögenswerte auf ein auf seinen Namen lautendes Konto bei der damaligen B._ Bank veranlasst. Weitere zur Verfügung gestellte Geldsummen, welche er ebenfalls auf das Konto bei der Bank A._ AG hätte überweisen müssen, habe er ohne Wissen und Willen von Y._ auf ein eigenes Konto bei der C._ Bank SA einbezahlt. X._ habe dadurch Y._ einen Vermögensschaden von (umgerechnet) rund Fr. 3.3 Mio. zugefügt.
B. Das Strafgericht Basel-Stadt sprach X._ mit Entscheid vom 8. Juli 2008 des gewerbsmässigen Betrugs, der Veruntreuung sowie der mehrfachen Urkundenfälschung schuldig. Es verurteilte ihn zu einer Freiheitsstrafe von drei Jahren, teilbedingt vollziehbar bei einer Probezeit von zwei Jahren. Den zu vollziehenden Teil der Freiheitsstrafe legte es auf ein Jahr fest. Vom Vorwurf der Veruntreuung einer Zeichnung (Anklageschrift Ziffer I. lit. D) sprach es ihn frei. Weiter verpflichtete es ihn, Y._ Schadenersatz im Umfang von Fr. 3'280'452.75 nebst Zins zu bezahlen. Eine darüber hinausgehende Forderung verwies das Strafgericht auf den Zivilweg. Zudem ordnete es an, die beschlagnahmten Vermögenswerte bei der D._ Bank AG an Y._ a conto Schadenersatzforderung zurückzugeben.
Die dagegen von X._ erhobene Berufung hiess das Appellationsgericht des Kantons Basel-Stadt mit Urteil vom 5. November 2010 teilweise gut. Es sprach ihn der mehrfachen Veruntreuung und der mehrfachen Urkundenfälschung schuldig und verurteilte ihn zu einer Freiheitsstrafe von zwei Jahren und 10 Monaten, teilbedingt vollziehbar bei einer Probezeit von zwei Jahren. Den zu vollziehenden Teil der Freiheitsstrafe legte es auf 10 Monate fest. Vom Vorwurf des gewerbsmässigen Betrugs sprach es ihn frei. Im Übrigen bestätigte das Appellationsgericht den erstinstanzlichen Entscheid.
C. X._ führt Beschwerde in Strafsachen. Er beantragt im Wesentlichen, das Urteil des Appellationsgerichts des Kantons Basel-Stadt sei in Bezug auf den Vorwurf der mehrfachen Veruntreuung mangels Zuständigkeit aufzuheben. Er sei wegen Urkundenfälschung zu einer teilbedingten Freiheitsstrafe von 12 Monaten zu verurteilen. Eventualiter sei die Sache an die Vorinstanz zurückzuweisen, um ihn vom Vorwurf der Veruntreuung freizusprechen. Die Forderung von Y._ sei auf den Zivilweg zu verweisen. Weiter beantragt er betreffend die Herausgabe der bei der D._ Bank AG beschlagnahmten Vermögenswerte sinngemäss die aufschiebende Wirkung. Diese wurde am 15. Februar 2011 superprovisorisch erteilt. Endlich ersucht er um Aktenbeizug beim Zivilgericht Basel-Stadt und um Sistierung des bundesgerichtlichen Verfahrens.
D. Der Präsident der strafrechtlichen Abteilung hat auf Gesuch hin mit Verfügung vom 15. März 2011 der Beschwerde in Bezug auf die Herausgabe der beschlagnahmten Vermögenswerte die aufschiebende Wirkung erteilt.
E. Das Appellationsgericht des Kantons Basel-Stadt und Y._ beantragen in ihren Vernehmlassungen, die Beschwerde sei abzuweisen. Die Staatsanwaltschaft des Kantons Basel-Stadt beantragt ebenfalls die Abweisung der Beschwerde und verzichtet im Übrigen auf eine Stellungnahme.

Erwägungen:
1. In tatsächlicher Hinsicht geht die Staatsanwaltschaft des Kantons Basel-Stadt in der Anklageschrift vom 1. September 2005 von folgendem Sachverhalt aus: Der Beschwerdeführer eröffnete am 27. März 1995 bei der Bank A._ AG in Basel auf seinen Namen ein Konto. Y._ (nachfolgend: Beschwerdegegnerin 2) räumte er eine Vollmacht mit Einzelzeichnungsberechtigung ein und bezeichnete sie mittels Formular A ("Identification de l'ayant droit économique") als wirtschaftlich Berechtigte. In der Folge empfing der Beschwerdeführer von der Beschwerdegegnerin 2 mehrere Geldbeträge jeweils mit der Verpflichtung, diese auf das eigens zwecks Gutschrift dieser Geldsummen eröffnete Konto in der Schweiz einzubezahlen.
1.1 In der Zeit ab 9. Oktober 1995 bis zum 1. September 1997 stellte die Beschwerdegegnerin 2 dem Beschwerdeführer 11 Beträge in der Gesamthöhe von (umgerechnet) rund Fr. 2.7 Mio. zur Verfügung. Die ersten Gelder (Ziffer 1.1. der Anklageschrift) stammten von Offshore-Gesellschaften, die folgenden Beträge (Ziffer 1.2. - 1.11.) übergab sie ihm jeweils bar in Paris. Die Vermögenswerte zahlte der Beschwerdeführer zur Hauptsache und instruktionsgemäss auf das Konto bei der Bank A._ AG in Basel ein. Einzelne Teilbeträge verwendete er vereinbarungswidrig für eigene Zwecke. Am 24. September 1997 verlangte er ohne Wissen und Willen der Beschwerdegegnerin 2 bei der Bank A._ AG die Saldierung des Kontos und wies die Bank an, die Vermögenswerte zu Gunsten eines auf seinen Namen lautenden Kontos bei der damaligen B._ Bank in Basel zu vergüten.
1.2 Zwischen Ende April und Anfang Mai 1998 liess der Beschwerdeführer, so die Staatsanwaltschaft, die Konten bei der E._ Bank AG saldieren und die Gelder auf ein neu eröffnetes Konto bei der C._ Bank SA in Genf übertragen. Als wirtschaftlich Berechtigten bezeichnete er sich selbst. Die Beschwerdegegnerin 2 übergab ihm vom Mai 1998 bis August 1998 drei weitere Beträge in der Gesamthöhe von (umgerechnet) rund Fr. 590'000.-- zwecks Vermögensverwaltung und Einzahlung auf das (nicht mehr bestehende) Konto bei der Bank A._ AG. Das Geld überwies der Beschwerdeführer zur Hauptsache auf das Konto bei der C._ Bank SA. Im Mai 2000 liess er die Konten bei der C._ Bank SA saldieren und das Guthaben zur D._ Bank AG in Genf übertragen. Bis zur Beschlagnahmung der Vermögenswerte am 10. Oktober 2003 bezog der Beschwerdeführer von diesem Konto rund Fr. 475'000.--.
2. 2.1 Der Beschwerdeführer macht geltend, die Vorinstanz habe zu Unrecht die schweizerische Gerichtsbarkeit bejaht. Er rügt sinngemäss eine Verletzung der Art. 3 und Art. 7 aStGB respektive Art. 3 und Art. 8 StGB. Zur Begründung führt er an, in der Überweisung von einer Basler Bank (Bank A._ AG) auf die andere (B._ Bank) sei kein fehlender Rückgabewille oder eine Vereitelung des Rückgabeanspruchs zu sehen. Auch sei kein Beweis erbracht für eine Instruktion durch die Beschwerdegegnerin 2, Gelder in die Schweiz zu bringen. Deshalb sei - gehe man von den bestrittenen Geldüberweisungen in Paris aus - das Delikt in Frankreich vollendet und beendet worden. Die Beschwerdegegnerin 2 habe zu keiner Zeit eine Zugriffsmöglichkeit auf die fraglichen Guthaben gehabt. In Bezug auf die Zahlungen ab Mai 1998 sei es willkürlich anzunehmen, er sei erst in Genf durch die Einzahlung auf die C._ Bank SA bereichert worden. Er habe bereits in Paris über die Geldsummen verfügen können. Deshalb sei bereits dort eine Bereicherung eingetreten (Beschwerde S. 3 ff.).
2.2 Die Vorinstanz erwägt, die Beschwerdegegnerin 2 habe Zugriff auf die Vermögenswerte bei der Bank A._ AG gehabt. Somit sei ihr nicht bereits mit der Übergabe der Gelder an den Beschwerdeführer in Paris der Zugriff verunmöglicht worden. Vielmehr sei dies erst erfolgt mit der Saldierung des Kontos bei der Bank A._ AG in Basel und mit der Übertragung der Vermögenswerte auf das Konto der B._ Bank in Basel. Darin liege eine Inlandtat im Sinne von <ref-law>. Betreffend die Zahlungen ab Mai 1998 (Anklageschrift Ziffer I. lit. B) habe die Beschwerdegegnerin 2 dem Beschwerdeführer die Beträge in Paris bar übergeben, worauf dieser sie in die Schweiz zur C._ Bank SA gebracht habe. Qualitativ liege kein entscheidender Unterschied zum Sachverhalt in <ref-ruling> vor, sei es dem Beschwerdeführer doch darum gegangen, die Bereicherung auf seine Konten in der Schweiz eintreten zu lassen. Der Ort der Bereicherung müsse auch beim Tatbestand der Veruntreuung als zuständigkeitsrechtlicher Anknüpfungspunkt gelten. Dazu komme, dass die Beschwerdegegnerin 2 in gewohnter Weise fortgefahren sei, dem Beschwerdeführer Geldbeträge auszuhändigen, welche dieser in der Schweiz anlegen sollte. Dass das Konto bei der Bank A._ AG unterdessen saldiert gewesen sei, habe sie nicht gewusst (angefochtenes Urteil S. 8 ff.).
2.3 Gemäss <ref-law> ist dem Schweizerischen Strafgesetzbuch unterworfen, wer in der Schweiz ein Verbrechen oder ein Vergehen verübt. Nach <ref-law> (Art. 7 Abs. 1 aStGB) gilt ein Verbrechen oder ein Vergehen als da begangen, wo der Täter es ausführt oder pflichtwidrig untätig bleibt, und da, wo der Erfolg eingetreten ist. Als Ausführung der Tat gilt jedes einzelne tatbestandsmässige Verhalten. Dabei genügt bereits eine teilweise Erfüllung des Tatbestands auf schweizerischem Gebiet, nicht aber der Entschluss der Tat oder die blosse Vorbereitungshandlung (<ref-ruling> E. 3c S. 253 mit Hinweisen; URSULA CASSANI, Die Anwendbarkeit des schweizerischen Strafrechts auf internationale Wirtschaftsdelikte, ZStrR 114/1996 S. 245 f.; vgl. auch CHRISTIAN SCHWARZENEGGER, Handlungs- und Erfolgsort beim grenzüberschreitenden Betrug, in: Wirtschaft und Strafrecht, Festschrift für Niklaus Schmid (...), 2001, S. 149 f.). Das Bundesgericht erwog in <ref-ruling> E. 6.3 S. 177, zur Vermeidung negativer Kompetenzkonflikte erscheine es im internationalen Verhältnis grundsätzlich geboten, auch in Fällen ohne engen Bezug zur Schweiz die schweizerische Zuständigkeit zu bejahen. Als Anknüpfungspunkt in der Schweiz genüge namentlich, dass im Ausland ertrogene Gelder auf einem Schweizer Bankkonto gutgeschrieben werden (vgl. auch Urteil 6B_178/2011 vom 20. Juni 2011 E.3).
2.3 Gemäss <ref-law> ist dem Schweizerischen Strafgesetzbuch unterworfen, wer in der Schweiz ein Verbrechen oder ein Vergehen verübt. Nach <ref-law> (Art. 7 Abs. 1 aStGB) gilt ein Verbrechen oder ein Vergehen als da begangen, wo der Täter es ausführt oder pflichtwidrig untätig bleibt, und da, wo der Erfolg eingetreten ist. Als Ausführung der Tat gilt jedes einzelne tatbestandsmässige Verhalten. Dabei genügt bereits eine teilweise Erfüllung des Tatbestands auf schweizerischem Gebiet, nicht aber der Entschluss der Tat oder die blosse Vorbereitungshandlung (<ref-ruling> E. 3c S. 253 mit Hinweisen; URSULA CASSANI, Die Anwendbarkeit des schweizerischen Strafrechts auf internationale Wirtschaftsdelikte, ZStrR 114/1996 S. 245 f.; vgl. auch CHRISTIAN SCHWARZENEGGER, Handlungs- und Erfolgsort beim grenzüberschreitenden Betrug, in: Wirtschaft und Strafrecht, Festschrift für Niklaus Schmid (...), 2001, S. 149 f.). Das Bundesgericht erwog in <ref-ruling> E. 6.3 S. 177, zur Vermeidung negativer Kompetenzkonflikte erscheine es im internationalen Verhältnis grundsätzlich geboten, auch in Fällen ohne engen Bezug zur Schweiz die schweizerische Zuständigkeit zu bejahen. Als Anknüpfungspunkt in der Schweiz genüge namentlich, dass im Ausland ertrogene Gelder auf einem Schweizer Bankkonto gutgeschrieben werden (vgl. auch Urteil 6B_178/2011 vom 20. Juni 2011 E.3).
2.4 2.4.1 Wie die Vorinstanz betreffend die ab 9. Oktober 1995 bis zum 1. September 1997 geleisteten Geldbeträge (Anklageschrift Ziffer I. lit. A) zu Recht erkennt, ergibt sich die Zuständigkeit der schweizerischen Behörden daraus, dass der Beschwerdeführer das Konto bei der Bank A._ AG in Basel im September 1997 eigenmächtig saldieren und die Vermögenswerte ohne Wissen und Willen der Beschwerdegegnerin 2 auf die B._ Bank in Basel transferieren liess. Letztere war einzig im Verkehr mit der Bank A._ AG einzelzeichnungsberechtigt und in Bezug auf das dort bestehende Konto laut Formular A wirtschaftlich Berechtigte. Dadurch schaffte der Beschwerdeführer das Vermögen beiseite. Soweit er in diesem Zusammenhang geltend macht, die Beschwerdegegnerin 2 habe (bereits) in Bezug auf das Konto bei der Bank A._ AG keine Möglichkeit gehabt, darauf zuzugreifen, weicht er in unzulässiger Weise vom verbindlichen Sachverhalt der Vorinstanz (<ref-law>) ab. Immerhin räumt auch der Beschwerdeführer ein, dass die Beschwerdegegnerin 2 von einem Konto bei der Bank A._ AG wusste. Ebenso wenig ist der Beschwerdeführer zu hören, soweit er eine Instruktion betreffend Geldtransfer von Frankreich in die Schweiz in Abrede stellt. Er bringt weiter vor, durch die Überweisung von einer Basler Bank auf die andere liege keine Vereitelung des Rückgabeanspruchs der Geldgeberin. Dies gelte für die Annahme, dass er die Gelder auf eine beliebige Bank habe anlegen können. Auch mit dieser Hypothese weicht er - ohne Willkür geltend zu machen - von den tatsächlichen Feststellungen der Vorinstanz ab, wonach die Beschwerdegegnerin 2 sämtliche Beträge allein zwecks Gutschrift auf das in ihrem Auftrag eröffnete Konto bei der Bank A._ AG zur Verfügung stellte.
2.4.2 Die Vorinstanz bejaht auch die Zuständigkeit der schweizerischen Gerichtsbehörden betreffend die ab 22. Mai 1998 geleisteten Geldsummen (Anklageschrift Ziffer I. lit. B) im Ergebnis zu Recht. Der Beschwerdeführer rügt zwar zutreffend, dass er (im Gegensatz zum Sachverhalt in <ref-ruling>) nicht erst mit der Überweisung auf ein Schweizer Konto auf die Gelder Zugriff hatte. Massgebend ist hingegen, dass die Vorinstanz die Handlungen des Beschwerdeführers betreffend die empfangenen Beträge von Mai bis August 1998 als Veruntreuung im Sinne von <ref-law> beurteilt. Zwar schafft die blosse, kurz vor den fraglichen Zahlungen erfolgte Eröffnung des Kontos bei der C._ Bank SA in Genf keinen Anknüpfungspunkt in der Schweiz, selbst wenn man diese als Vorbereitungshandlung qualifizieren wollte. Die Vorinstanz legt dem Beschwerdeführer jedoch zur Last, er habe das ihm anvertraute Vermögen auf ein der Beschwerdegegnerin 2 unbekanntes Konto bei der C._ Bank SA in Genf einbezahlt und konsequent bestritten, von ihr Geld entgegengenommen zu haben. Insbesondere durch die weisungswidrige Zahlung auf das Konto der C._ Bank SA habe er den Verbleib der Gelder gegenüber der Beschwerdegegnerin 2 verschleiert und seinen Willen manifestiert, ihren obligatorischen Rückerstattungsanspruch zu vereiteln (angefochtenes Urteil S. 32 f. mit Verweis auf S. 29 ff.). Der Beschwerdeführer beanstandet die rechtliche Beurteilung nicht. Auf die entsprechenden Erwägungen der Vorinstanz (angefochtenes Urteil S. 29 ff.) kann verwiesen werden (<ref-law>). Indem der Beschwerdeführer die Vermögenswerte zwecks Einzahlung auf das (nicht mehr bestehende) Konto bei der Bank A._ AG entgegennahm und diese auf das der Beschwerdegegnerin 2 unbekannte Konto der C._ Bank SA in Genf einzahlte, vollendete und beendete er die Veruntreuung im genannten Sinne. Mithin verhielt er sich tatbestandsmässig und führte er die Tat nebst in Paris teilweise in Genf aus. Damit liegt der Begehungsort gemäss <ref-law> respektive Art. 7 Abs. 1 aStGB in der Schweiz. Daran ändert entgegen dem Dafürhalten des Beschwerdeführers nichts, dass er bereits in Paris über den Geldbetrag verfügen konnte. Die Veruntreuung war zum damaligen Zeitpunkt noch nicht vollendet. Die von der Vorinstanz geprüfte Frage, ob der Ort, wo sich die Absicht des Täters verwirklichte oder verwirklichen sollte, als Erfolgsort im Sinne von <ref-law> gilt, braucht im Übrigen hier nicht aufgeworfen zu werden. Sie wird von der Rechtsprechung und dem überwiegenden Teil der Lehre bejaht (vgl. <ref-ruling> E. 2a S. 180; <ref-ruling> E. 3b/cc S. 214; je mit Hinweisen; GÜNTER STRATENWERTH, Schweizerisches Strafrecht, Die Straftat, 3. Aufl. 2005, § 5 Fn. 15 mit Hinweisen).
2.4.3 Die Vorinstanz nimmt zu Recht an, dass der Beschwerdeführer in Bezug auf die mehrfachen Veruntreuungen (Anklageschrift Ziffer I. lit. A und B) neben Paris auch in der Schweiz gehandelt hat.
3. 3.1 Betreffend die der Beschwerdegegnerin 2 zugesprochene Zivilforderung in der Höhe von Fr. 3'280'452.75 nebst Zins rügt der Beschwerdeführer eine Verletzung des rechtlichen Gehörs (<ref-law>). Die Beschwerdegegnerin 2 habe vor dem Zivilgericht Basel-Stadt eine Forderung in der Höhe von USD 2'950'000.-- anhängig gemacht, und das Zivilverfahren sei bis heute sistiert. Er habe wiederholt beantragt, die Akten des Verfahrens P.2005.195 vor dem Zivilgericht Basel-Stadt beizuziehen, was die Vorinstanz zu Unrecht unterlassen habe. Es sei unklar, ob die Beschwerdegegnerin 2 vor dem Zivilgericht und dem Strafgericht den gleichen Anspruch geltend mache. Deshalb seien die entsprechenden Zivilakten einzusehen. Das bundesgerichtliche Verfahren sei bis zur rechtskräftigen Erledigung des Verfahrens P.2005.195 respektive bis zum Abschluss der Beweisverfahren zu sistieren. Zudem sieht der Beschwerdeführer § 123 der Strafprozessordnung (des Kantons Basel-Stadt) vom 8. Januar 1997 (SG 257.100; aufgehoben per 1. Januar 2011) verletzt (Beschwerde S. 7 ff.).
3.2 Die Vorinstanz erwägt, der Beschwerdeführer habe mit Blick auf die behauptete gleichlautende Klage beim Zivilgericht Basel-Stadt darzutun und zu beweisen, dass die nämliche Streitsache schon rechtshängig gemacht worden sei. Dem Beschwerdeführer als beklagte Partei im Zivilprozess wäre es möglich gewesen, die Klageschrift im Strafverfahren einzureichen. Zudem handle es sich bei der beim Zivilgericht eingereichten Klage um eine Teilklage. Damit soll erlangt werden, was im Adhäsionsverfahren nicht zugesprochen werde (angefochtenes Urteil S. 12 f.).
3.3 Die Vorinstanz wirft dem Beschwerdeführer vor, es versäumt zu haben, die Klageschrift aus dem Zivilprozess im Strafprozess einzureichen respektive die Rechtshängigkeit zu beweisen. Dem kann aus verschiedenen Gründen nicht gefolgt werden:
Einerseits erhob der Beschwerdeführer ausdrücklich die Einrede der Litispendenz. Er hat damit vorgebracht, die Beschwerdegegnerin 2 habe die Zivilforderung in einem inzwischen sistierten Zivilprozess eingeklagt und damit rechtshängig gemacht. Eine Rechtshängigkeit ist - auch wenn das zweitangerufene Gericht regelmässig auf Hinweise des Beklagten angewiesen ist - als Prozessvoraussetzung von Amtes wegen zu beachten. Sie hat zur Folge, dass auf eine zweite identische Klage nicht einzutreten ist (<ref-ruling> E. 2b S. 283; vgl. § 60 der Zivilprozessordnung [des Kantons Basel-Stadt] vom 8. Februar 1875 [ZPO; SG 221.100; aufgehoben per 1. Januar 2011], Art. 35 des Bundesgesetzes vom 24. März 2000 über den Gerichtsstand in Zivilsachen [Gerichtsstandsgesetz; GestG; SR 272; aufgehoben per 1. Januar 2011] und <ref-law>/CH; FELIX DASSER, in: Kommentar Gerichtsstandsgesetz, 2001, N. 28 ff. zu Art. 35 GestG; MAZZUCCHELLI/POSTIZZI, in: Basler Kommentar, Schweizerische Strafprozessordnung, 2011, N. 14 zu <ref-law>; ANNETTE DOLGE, in: Basler Kommentar, a.a.O., N. 19 zu <ref-law>). Die Berücksichtigung von Amtes wegen folgt aus dem Umstand, dass dem Kläger für eine neue Klage gegen die gleiche Person und über denselben Gegenstand das Rechtsschutzinteresse fehlt (VOGEL/SPÜHLER, Grundriss des Zivilprozessrechts, 8. Aufl. 2006, N. 8.41 ff.; STAEHELIN/SUTTER, Zivilprozess nach den Gesetzen der Kantone Basel-Stadt und Basel-Landschaft unter Einbezug des Bundesrechts, 1992, § 18 N. 42; DASSER, a.a.O., N. 3 zu Art. 35 GestG). Falls die Beschwerdegegnerin 2 die adhäsionsweise im Strafverfahren eingeklagte Forderung vorgängig und identisch bereits beim Zivilgericht Basel-Stadt eingereicht hätte, könnte das später ersuchte Gericht, soweit das zuerst angerufene Gericht seine Zuständigkeit bejaht, auf diese nicht eintreten (zum Verfahren vgl. Art. 35 aGestG und <ref-law>/CH). Solches hat die Vorinstanz von Amtes wegen zu prüfen.
Andererseits geht die Vorinstanz - indem sie dem Beschwerdeführer vorwirft, die Litispendenz weder dargetan noch bewiesen zu haben - zumindest implizit davon aus, dass eine schriftliche Klagebegründung im Zivilprozess vorlag (vgl. angefochtenes Urteil S. 12 f. und Vernehmlassung vom 21. Februar 2011, wonach der Beschwerdeführer die Litispendenz "unschwer hätte selbst belegen können"). Ob die Zivilklage von der Beschwerdegegnerin 2 tatsächlich bereits begründet wurde, geht aus den Erwägungen der Vorinstanz hingegen nicht hervor. Die Beschwerdegegnerin 2 hält in ihrer Vernehmlassung fest, das Zivilverfahren sei vor der Klagebegründung sistiert worden. Entsprechende Abklärungen wurden durch die Vorinstanz, soweit ersichtlich, nicht getätigt. Die fragliche Zivilklage fällt grundsätzlich in die sachliche Zuständigkeit der Zivilgerichts-Kammer (vgl. § 27 ff. des Gesetzes [des Kantons Basel-Stadt] vom 27. Juni 1895 betreffend Wahl und Organisation der Gerichte sowie der Arbeitsverhältnisse des Gerichtspersonals und der Staatsanwaltschaft [Gerichtsorganisationsgesetz; GOG; SG 154.100; aufgehoben per 1. Januar 2011]). Die basel-städtische Zivilprozessordnung sah Ausnahmen von der sofortigen schriftlichen Klagebegründung vor der Zivilgerichts-Kammer vor. Insbesondere konnte die Begründung unterbleiben, wenn mit der Klage gleichzeitig ein Gesuch um Vermittlung gestellt wurde (<ref-law>/BS; vgl. STAEHELIN/SUTTER, a.a.O., § 16 N. 6). Das Zivilgericht Basel-Stadt führte am 23. April 2007 eine Vermittlungsverhandlung im Sinne von <ref-law>/BS durch und sistierte das Verfahren im Anschluss daran (act. 9). Deshalb ist es nicht ausgeschlossen, dass eine Klagebegründung gar nicht vorlag. Selbstredend wäre es dem Beschwerdeführer in diesem Fall nicht möglich, Ausführungen zur Klageidentität zu machen respektive eine solche zu beweisen. Entsprechendes hat die Vorinstanz von Amtes wegen zu prüfen. Sie kann es nicht mit der blossen Parteibehauptung der Beschwerdegegnerin 2 im Strafverfahren bewenden lassen, ihre Klage vor Zivilgericht sei eine Teilklage und mit der Adhäsionsklage nicht identisch.
Die Vorinstanz verletzt das rechtliche Gehör des Beschwerdeführers, indem sie zur Frage der Litispendenz die Akten des Verfahrens P.2005.195 vor dem Zivilgericht Basel-Stadt nicht beizieht und die Prozessvoraussetzungen nicht prüft (vgl. zum Recht des Betroffenen, mit erheblichen Beweisanträgen gehört zu werden, <ref-ruling> E. 3.2 S. 272 mit Hinweisen). Entsprechendes hat sie nachzuholen. Für einen Aktenbeizug durch das Schweizerische Bundesgericht besteht keine Veranlassung. Ebenso wenig ist eine Sistierung des bundesgerichtlichen Verfahrens zweckmässig (<ref-law> in Verbindung mit <ref-law>). Der Fall ist betreffend Zivilpunkt von der Vorinstanz neu zu beurteilen und für das Schweizerische Bundesgericht spruchreif.
3.4 Auf die Rüge der Verletzung von § 123 aStPO/BS ist nicht einzutreten. Das Bundesgericht kann die Anwendung kantonalen Rechts nicht frei prüfen, wie sich aus <ref-law> ergibt. Es kann nur prüfen, ob die Vorinstanz das kantonale Recht willkürlich angewendet und dadurch das Willkürverbot (<ref-law>) verletzt hat. Dies wird aber vom Beschwerdeführer nicht einmal geltend gemacht.
4. 4.1 Der Beschwerdeführer behauptet, die auf das Konto der Bank A._ AG und der C._ Bank SA einbezahlten Beträge stammten aus seinem Vermögen. Er wirft der Vorinstanz eine willkürliche Beweiswürdigung (<ref-law>) sowie die Verletzung der Unschuldsvermutung (<ref-law> und Art. 6 Ziff. 2 EMRK) und des rechtlichen Gehörs (<ref-law>) vor.
4.2 Die vorinstanzliche Sachverhaltsfeststellung kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; vgl. auch Art. 105 Abs. 1 und 2 BGG). Offensichtlich unrichtig im Sinne von <ref-law> ist die Sachverhaltsfeststellung, wenn sie willkürlich ist (<ref-ruling> E. 1.4.1 S. 39; vgl. zum Begriff der Willkür <ref-ruling> E. 4.2 S. 560 mit Hinweisen).
Ebenfalls nur unter dem Gesichtspunkt der Willkür prüft das Bundesgericht, inwiefern das Sachgericht den Grundsatz "in dubio pro reo" als Beweiswürdigungsregel verletzt hat. Diese aus der Unschuldsvermutung (<ref-law> und Art. 6 Ziff. 2 EMRK) abgeleitete Maxime wurde wiederholt dargelegt, worauf zu verweisen ist (<ref-ruling> E. 2a S. 40 f. mit Hinweisen).
Wird die Verletzung von Grundrechten (einschliesslich der willkürlichen Anwendung von kantonalem Recht und Willkür bei der Sachverhaltsfeststellung) gerügt, gelten qualifizierte Anforderungen an die Begründung. Eine solche Rüge prüft das Bundesgericht nicht von Amtes wegen, sondern nur, wenn sie in der Beschwerde vorgebracht und substanziiert begründet worden ist. Das bedeutet, dass klar und detailliert anhand der Erwägungen des angefochtenen Entscheids darzulegen ist, inwiefern verfassungsmässige Rechte verletzt worden sein sollen (<ref-law>; <ref-ruling> E. 4.2.3 S. 5; <ref-ruling> E. 1.3.1 S. 68; je mit Hinweisen).
4.3 Es reicht für die Rüge einer willkürlichen Beweiswürdigung nicht aus, wenn der Beschwerdeführer zum Beweisergebnis wie in einem appellatorischen Verfahren frei plädiert und darlegt, wie seiner Auffassung nach die vorhandenen Beweise (insbesondere die Bankunterlagen der F._ Bank sowie die Aussagen verschiedener Zeugen) richtigerweise zu würdigen gewesen wären. Der Beschwerdeführer behauptet beispielsweise, an der Echtheit der von der Beschwerdegegnerin 2 eingereichten Bankbelege bestünden erhebliche Zweifel, und jene sei rechtshilfeweise zu überprüfen. Damit wiederholt er sein Vorbringen im kantonalen Verfahren. Das Strafgericht Basel-Stadt, auf dessen Ausführungen die Vorinstanz verweist, erwägt dazu insbesondere Folgendes: Die Beschwerdegegnerin 2 hätte sämtliche Auszüge der F._ Bank, der G._ Bank und der H._ Bank fälschen müssen. Sie hätte die so dokumentierten Ausgänge mit den Einzahlungen auf das Konto bei der Bank A._ AG zeitlich und dem Betrag nach abstimmen müssen, ohne die Auszüge der Bank A._ AG zu Gesicht zu bekommen. Es könne nicht vernünftig erklärt werden, wie solches überhaupt möglich sein soll (angefochtenes Urteil S. 26 mit Verweis auf den erstinstanzlichen Entscheid S. 20 f.). Der Beschwerdeführer setzt sich mit diesen Erwägungen nicht auseinander, sondern stellt ihnen einzig seine eigene, davon abweichende Auffassung gegenüber. Eine Verfassungs- oder Konventionsverletzung zeigt er dadurch nicht auf. Zudem ist mit Blick auf das Eingeständnis des Beschwerdeführers, Bankbelege seines Kontos bei der I._ Bank gefälscht zu haben, um fingierte Bezüge den jeweiligen Einzahlungen bei der Bank A._ AG gegenüberzustellen, wenig überzeugend, dass die Unterlagen betreffend die Bezüge bei den drei genannten Banken der Beschwerdegegnerin 2 ebenfalls gefälscht sein sollten.
Die Ausführungen des Beschwerdeführers (Beschwerde S. 9 ff.) sind im Übrigen wenig substanziiert und genügen den qualifizierten Begründungsanforderungen im Sinne von <ref-law> nicht. Dies trifft beispielsweise auf die Behauptung zu, die Beschwerdegegnerin 2 habe Kopien von Dokumenten eingereicht, welche "immer den gleichen Kontosaldo ausweisen", diese würden "keine Deckung für die behauptete Abhebung vorweisen", und es sei willkürlich, dass "eine Indizienkette [...] ohne genaue Untersuchung der Umstände jeder einzelnen Zahlung pauschal zu Gunsten der Geschädigten ausgelegt wird." Damit ist der Beschwerdeführer nicht zu hören. Soweit die Vorinstanz festhält, das verwendete Formular A zur Identifizierung des wirtschaftlich Berechtigten entfalte keine zivilrechtliche Wirkung, könne aber als Indiz zu Gunsten der Beschwerdegegnerin 2 herangezogen werden, ist dies entgegen dem Dafürhalten des Beschwerdeführers nicht zu beanstanden.
Insgesamt zeigt der Beschwerdeführer nicht auf, dass und inwiefern das vorinstanzliche Beweisergebnis schlechterdings nicht mehr vertretbar sein sollte, und eine Verletzung der Unschuldsvermutung ist nicht ersichtlich. Die Vorinstanz durfte willkürfrei in vorweggenommener Beweiswürdigung von einem Rechtshilfeersuchen betreffend die Bankbelege der F._ Bank absehen. Eine Verletzung des rechtlichen Gehörs liegt nicht vor (vgl. zum Recht des Betroffenen, mit erheblichen Beweisanträgen gehört zu werden, sowie zur antizipierten Beweiswürdigung <ref-ruling> E. 3.2 S. 272, 229 E. 5.3 S. 236 f.; je mit Hinweisen). Die Beschwerde erweist sich daher als unbegründet, soweit sie den Begründungsanforderungen von Art. 42 Abs. 2 und <ref-law> überhaupt zu genügen vermag.
5. Auf das Rechtsbegehren des Beschwerdeführers, er sei wegen Urkundenfälschung zu einer teilbedingten Freiheitsstrafe von 12 Monaten zu verurteilen, ist nicht einzutreten. Dieses wird in der Beschwerde nur mit dem beantragten Freispruch vom Vorwurf der mehrfachen Veruntreuung begründet. Es bleibt aber bei der Verurteilung des Beschwerdeführers.
6. Der Beschwerdeführer obsiegt, soweit er betreffend das Verfahren vor dem Zivilgericht Basel-Stadt (P.2005.195) eine Verletzung des rechtlichen Gehörs durch die Vorinstanz rügt. Die Beschwerde ist teilweise gutzuheissen, das angefochtene Urteil aufzuheben und die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Im Übrigen ist die Beschwerde abzuweisen, soweit darauf einzutreten ist.
7. Der Beschwerdeführer und die Beschwerdegegnerin 2 werden im Umfang ihres Unterliegens kostenpflichtig (<ref-law>). Die Gerichtskosten sind zu drei Vierteln dem Beschwerdeführer und zu einem Achtel der Beschwerdegegnerin 2 aufzuerlegen. Der Kanton Basel-Stadt hat keine Verfahrenskosten zu tragen (<ref-law>). Der Beschwerdeführer stellt ein Gesuch, die Verfahrenskosten erst nach seiner Freilassung begleichen zu können. Nebst einer französischen Rente bestreite er seinen Lebensunterhalt mit "Mitteln aus Algerien, über welche er nur in bar verfügen" könne. Über das Stundungsbegehren ist hier nicht zu entscheiden. Dem Beschwerdeführer steht es frei, ein entsprechendes Gesuch an die Bundesgerichtskasse zu stellen und zu belegen. Bei der Bemessung der Gerichtskosten ist nicht von angespannten finanziellen Verhältnissen auszugehen. Dass (nebst der französischen Rente) die Mittel aus Algerien knapp bemessen wären, behauptet der Beschwerdeführer nicht.
Der Kanton Basel-Stadt und die Beschwerdegegnerin 2 haben als teilweise unterliegende Parteien dem Beschwerdeführer eine reduzierte Parteientschädigung von je einem Achtel der auf Fr. 3'000.-- bestimmten Entschädigung zu bezahlen (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Das Sistierungsgesuch wird abgewiesen.
2. Die Beschwerde wird teilweise gutgeheissen, das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 5. November 2010 aufgehoben und die Sache im Sinne der Erwägungen zur neuen Entscheidung an die Vorinstanz zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen, soweit darauf einzutreten ist.
3. Die Gerichtskosten werden im Umfang von Fr. 3'000.-- dem Beschwerdeführer und im Umfang von Fr. 500.-- der Beschwerdegegnerin 2 auferlegt.
4. Der Kanton Basel-Stadt hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 375.-- zu entschädigen.
5. Die Beschwerdegegnerin 2 hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 375.-- zu entschädigen.
6. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 13. September 2011
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Der Gerichtsschreiber: Faga