Sachverhalt: A. Die Staatsanwaltschaft des Kantons Zug führte gegen den deutschen Staatsbürger X._ eine Strafuntersuchung wegen gewerbsmässigen Betrugs und mehrfacher ungetreuer Geschäftsbesorgung. Als dieser seinen Wohnsitz nach Deutschland verlegte, ersuchte die Staatsanwaltschaft des Kantons Zug den Leitenden Oberstaatsanwalt in Köln darum, die Strafverfolgung zu übernehmen. Nach Abtretung der Strafverfolgung an die deutschen Strafverfolgungsbehörden wurde das in Zug anhängige Verfahren sistiert. Der Leitende Oberstaatsanwalt in Köln stellte das Ermittlungsverfahren gegen X._ am 24. August 2012 mangels hinreichenden Tatverdachts ein. Mit Verfügung vom 11. Februar 2015 stellte die Staatsanwaltschaft des Kantons Zug das wieder aufgenommene Verfahren gegen X._ ein und auferlegte ihm die Kosten der Untersuchung von Fr. 116'613.10. Dagegen erhob X._ Beschwerde. Das Obergericht des Kantons Zug hiess diese am 21. Oktober 2015 teilweise gut. Es auferlegte X._ die Kosten des Untersuchungsverfahrens nur zu sechs Zehntel und nahm den Rest auf die Staatskasse. Für die Kosten des Beschwerdeverfahrens nahm es dieselbe Aufteilung vor. B. X._ beantragt mit Beschwerde in Strafsachen, das obergerichtliche Urteil sei in Bezug auf die Kostenverlegung aufzuheben und die gesamten Kosten des Verfahrens seien auf die Staatskasse zu nehmen. C. Das Obergericht des Kantons Zug beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei, und verweist auf die Erwägungen im angefochtenen Entscheid. Die Staatsanwaltschaft schliesst ebenfalls auf Abweisung der Beschwerde. X._ erhielt Gelegenheit, zu den Vernehmlassungen Stellung zu nehmen.