Sachverhalt: A. Mit Verfügung der Staatsanwaltschaft Zürich-Sihl vom 21. Januar 2009 wurde die gegen X._ geführte Strafuntersuchung wegen Betrugs etc. eingestellt. Die Verfahrenskosten wurden zur Hälfte X._ und zu je einem Viertel den beiden Anzeigeerstatterinnen auferlegt. Eine Entschädigung wurde X._ nicht zugesprochen. Den von den beiden Anzeigeerstatterinnen gegen die Einstellung der Strafuntersuchung erhobenen Rekurs wies das Obergericht des Kantons Zürich ab. Zudem stellten sowohl X._ als auch die beiden Anzeigeerstatterinnen das Begehren um gerichtliche Beurteilung der Kosten- und Entschädigungsfolgen. Mit Verfügung vom 16. Juni 2010 bestätigte die Einzelrichterin in Zivil- und Strafsachen des Bezirks Zürich die in der Einstellungsverfügung vom 21. Januar 2009 getroffene Kosten- und Entschädigungsregelung. B. Gegen diese Verfügung führte X._ Rekurs ans Obergericht. Er beantragte die Aufhebung der Kostenauflage, die Zusprechung einer Entschädigung von Fr. 121'632.-- für die Aufwendungen seiner Verteidigung sowie die Ausrichtung von Schadenersatz in der Höhe von EUR 80'376.-- und einer Genugtuung im Betrag von Fr. 10'000.--. Mit Beschluss vom 24. Oktober 2011 hiess das Obergericht den Rekurs teilweise gut und hob die Verfügung der Einzelrichterin vom 16. Juni 2010 teilweise auf. Das Obergericht nahm die Verfahrenskosten zur Hälfte auf die Staatskasse und auferlegte sie zu je einem Viertel den beiden Anzeigeerstatterinnen. Des Weiteren sprach es X._ Schadenersatz für seine anwaltlichen Aufwendungen von Fr. 75'000.-- und eine Genugtuung von Fr. 5'000.-- zu, beides zuzüglich Zins zu 5 % ab 21. Januar 2009. C. Mit Beschwerde ans Bundesgericht vom 25. November 2011 ficht X._ den Beschluss des Obergerichts vom 24. Oktober 2011 an und beantragt, die Staatsanwaltschaft sei in Ergänzung des vorinstanzlichen Beschlussdispositivs zu verpflichten, ihm zusätzlich zum Schadenersatz von Fr. 75'000.-- und zur Genugtuung von Fr. 5'000.-- den Betrag von EUR 80'376.--, zuzüglich Zins zu 5 % ab 21. Januar 2009, aus der Staatskasse auszurichten. Das Obergericht und die Staatsanwaltschaft verzichten auf Stellungnahmen zur Beschwerde.