Sachverhalt:
A. X._ drohte am Abend des 19. Oktobers 2007 im Restaurant R._ in S._ in stark alkoholisiertem Zustand der Wirtin W._, ihr Lokal zu demolieren. Zudem stiess er gegen seine - nicht anwesende - Ex-Freundin F._ eine Todesdrohung aus. Anschliessend weigerte er sich, den ausgerückten Polizeibeamten zu folgen. X._ wurde am 30. Oktober 2007 verhaftet. Am 24. Januar 2008 zog die Geschädigte W._ ihren Strafantrag zurück. Die Geschädigte F._ erteilte am 1. Februar 2008 die Zustimmung zur Einstellung des Verfahrens im Sinne von <ref-law>.
B. Das Bezirksgericht Bülach sprach X._ am 25. August 2008 der Drohung sowie der Hinderung einer Amtshandlung schuldig und verurteilte ihn zu einer unbedingten Freiheitsstrafe von 5 Monaten. Es nahm davon Vormerk, dass die Strafe durch die erstandene Polizeiverhaft, Untersuchungs- und Sicherheitshaft von insgesamt 301 Tagen vollumfänglich erstanden war.
C. X._ erhob Berufung ans Obergericht des Kantons Zürich, wobei er den Schuldspruch wegen Hinderung einer Amtshandlung ausdrücklich akzeptierte. Das Obergericht stellte mit Beschluss vom 31. Mai 2010 das Strafverfahren wegen Drohung definitiv ein. Mit Urteil des gleichen Tages bestrafte es X._ mit einer bedingten Geldstrafe von 15 Tagessätzen. Es legte die Kosten der Untersuchung und des erstinstanzlichen Verfahrens zu 1/10 X._ auf und nahm sie zu 9/10 auf die Gerichtskasse. Das Obergericht sprach X._ Fr. 26'600.-- Schadenersatz sowie Fr. 45'000.-- Genugtuung zu, je nebst Zins zu 5 % seit dem 1. Mai 2008.
D. Mit Beschwerde in Strafsachen beantragt die Oberstaatsanwaltschaft des Kantons Zürich, das Urteil des Obergerichts sei aufzuheben und kassatorisch zu neuer Entscheidung an die Vorinstanz zurückzuweisen.
E. X._ beantragt die Abweisung der Beschwerde. Zudem stellt er ein Gesuch um unentgeltliche Rechtspflege und Verbeiständung. Die Vorinstanz verzichtet auf Vernehmlassung.

Erwägungen:
1. Die Beschwerdeführerin rügt eine willkürliche Anwendung des kantonalen Prozessrechts bei der Bemessung der Genugtuungssumme.
1.1 Das angefochtene Urteil ist vor dem Inkrafttreten der Schweizerischen Strafprozessordnung vom 5. Oktober 2007 (Strafprozessordnung, StPO; SR 312.0) am 1. Januar 2011 ergangen. Die vorliegende Beschwerde ist deshalb nach bisherigem Recht zu beurteilen (<ref-law>).
Gemäss § 191 Satz 1 i.V.m. § 43 Abs. 1 der Strafprozessordnung des Kantons Zürich vom 4. Mai 1919 (StPO/ZH; LS 321) ist darüber zu entscheiden, ob einem freigesprochenen Angeklagten, welchem die Kosten nicht auferlegt werden, eine Entschädigung für die durch die Untersuchung verursachten Kosten und Umtriebe sowie eine Genugtuung auszurichten ist. Laut <ref-law>/ZH hat ein Angeschuldigter, der durch das Verfahren in seinen persönlichen Verhältnissen schwer verletzt worden ist, Anspruch auf Ausrichtung einer angemessenen Geldsumme als Genugtuung.
1.2 Die Genugtuungsforderung hat insoweit einen Zusammenhang mit dem Strafverfahren, als sie ihren Rechtsgrund in einem (rechtmässigen oder rechtswidrigen) Verhalten der Strafverfolgungsbehörden und der dadurch bewirkten seelischen Unbill hat. Der Sache nach handelt es sich um einen Haftungsanspruch gegen den Kanton Zürich, mithin um ein auf kantonales öffentliches Recht gestützter vermögensrechtlicher Anspruch. Sie unterliegt daher grundsätzlich der dafür vorgesehenen Beschwerde in öffentlich-rechtlichen Angelegenheiten im Sinne der <ref-law>. Für deren Behandlung ist die Strafrechtliche Abteilung zuständig (Art. 30 Abs. 1 lit. c Ziff. 1 und Art. 33 des Reglements für das Bundesgericht vom 20. November 2006 [BGerR; SR 173.110.131]; <ref-ruling> E. 1.1.2 S. 46 mit Hinweisen).
1.3 Nach dem Gesagten ist nicht die Beschwerde in Strafsachen (<ref-law>) gegeben, sondern jene in öffentlich-rechtlichen Angelegenheiten (<ref-law>). Die falsche Bezeichnung des Rechtsmittels schadet nicht, sofern die Eintretensvoraussetzungen des Rechtsmittels, das hätte eingereicht werden müssen, erfüllt sind (<ref-ruling> E. 1.2 S. 382 mit Hinweisen). Die Ergreifung der Beschwerde in öffentlich-rechtlichen Angelegenheiten setzt einen Streitwert von mindestens Fr. 30'000.-- voraus (<ref-law>), der hier erreicht ist.
2. 2.1 Die Vorinstanz führt aus, der Beschwerdegegner habe die Einleitung des Strafverfahrens durch sein verwerfliches Benehmen verursacht. Insoweit seien ihm grundsätzlich die bis zum 24. Januar 2008 (Rückzug des Strafantrags der Geschädigten W._) bzw. 1. Februar 2008 (Zustimmung der Geschädigten F._ zur Einstellung des Verfahrens) aufgelaufenen Kosten aufzuerlegen. Da es im Nachhinein als vertretbar und insofern gerechtfertigt erscheine, dass der Beschwerdegegner Ende Oktober 2007 in Untersuchungshaft versetzt worden sei, habe er für die entsprechenden Kosten selber aufzukommen. Indessen hätte nach dem 1. Februar 2008 das Strafverfahren - mit Ausnahme der Hinderung einer Amtshandlung - eingestellt werden können. Ab da an habe weder ein Haftgrund noch die Notwendigkeit einer amtlichen Verteidigung bestanden. Vor diesem Hintergrund seien die Kosten der Untersuchung und der amtlichen Verteidigung nur zu 1/10 dem Beschwerdegegner aufzuerlegen und im Übrigen auf die Gerichtskasse zu nehmen. Bei einer teilweisen Kostenauflage stelle sich die Frage, ob dem Beschwerdegegner Anspruch auf Schadenersatz und Genugtuung zustehe. Beim Anspruch auf Haftentschädigung komme sowohl Ersatz von Vermögensschaden als auch Genugtuung für schwerwiegende immaterielle Nachteile in Frage. Nach Abzug der Geldstrafe wegen Hinderung einer Amtshandlung resultiere eine Überhaft von 286 Tagen bzw. von rund 91⁄2 Monaten. Da es gute Gründe gegeben habe, den Beschwerdegegner zu inhaftieren, habe er einen daraus erwachsenen Schaden primär selber zu vertreten. Zu prüfen sei, welchen Einkommensverlust er infolge der unrechtmässig erlittenen Überhaft ab 1. Februar 2008 von knapp 7 Monaten erlitten habe. Dafür ergebe sich ein Schadenersatz von Fr. 26'600.--. Bei der Bemessung der Genugtuung sei zu berücksichtigen, dass die Fortsetzung der Untersuchungshaft nach dem 1. Februar 2008 gesetzeswidrig gewesen sei. Dem Beschwerdegegner seien nur Drohungen vorgeworfen worden. Die Inhaftierung habe er durch verwerfliches und zugleich rechtswidriges Verhalten selber verursacht. Es erscheine angemessen, für die gesamte Überhaft von 286 Tagen - unter Berücksichtigung der ab 1. Februar 2008 rechtswidrigen Haft und sämtlicher mit dem Verfahren verbundenen Unbill - eine Genugtuung von Fr. 45'000.-- zuzusprechen (angefochtenes Urteil E. IV. 2 und 3 S. 12 ff.).
2.2 Die Beschwerdeführerin bringt vor, aus dem klaren Wortlaut der §§ 191 und 43 StPO/ZH ergebe sich, dass einer beschuldigten Person nur für jenen Zeitraum des Verfahrens ein Anspruch auf Entschädigung und Genugtuung zustehe, für welchen ihr keine Kosten auferlegt würden. Die Vorinstanz sei zutreffend davon ausgegangen, dass dem Beschwerdegegner aufgrund seines verwerflichen Benehmens die bis zum 1. Februar 2008 aufgelaufenen Kosten aufzuerlegen seien. Sie habe deshalb nur Schadenersatz für die unrechtmässig erlittene Haft ab dem 1. Februar 2008 zugesprochen. In Widerspruch zu diesen Erwägungen habe die Vorinstanz die Genugtuung für die gesamte Überhaft von 286 Tagen bemessen. Indem die Vorinstanz die Genugtuungssumme nicht massiv reduziert habe, habe sie den Beschwerdegegner in unzulässiger Weise begünstigt. Der Betrag sei krass zu hoch festgesetzt und stütze sich auf eine willkürliche Anwendung des kantonalen Prozessrechts. Die Strafsache sei an die Vorinstanz zur willkürfreien Festsetzung der Genugtuungssumme zurückzuweisen.
2.3 Aus der Praxis des Bundesgerichtes lässt sich der Grundsatz ableiten, dass demjenigen, der zu Unrecht einer schweren Straftat verdächtigt und deshalb ungerechtfertigt inhaftiert worden ist, ein gewisser Mindestbetrag als Genugtuung zustehen muss, sofern eine Gesetzesgrundlage für eine entsprechende Entschädigung für rechtmässige aber unverschuldete Haft besteht. Dieser Mindestbetrag ist nach Massgabe der Dauer der vollzogenen Haft zu erhöhen. Da die Tatsache der schweren strafrechtlichen Verdächtigung einen Hauptbestandteil des erlittenen "tort moral" ausmacht, wäre jedoch eine lineare Erhöhung des erwähnten Grundbetrages nicht gerechtfertigt. Im Sinne dieser Praxis ist für die Tatsache der Inhaftierung wegen Verdachts einer schweren Straftat ein gewisser minimaler Grundbetrag von jedenfalls einigen tausend Franken zuzusprechen, der aufgrund der erlittenen Haft und der damit zusätzlich verbundenen immateriellen Beeinträchtigungen heraufzusetzen ist. Dabei ist jedoch keine "lineare" Multiplikation mit der Anzahl der Hafttage vorzunehmen (<ref-ruling> E. 3b S. 156; Urteil 8G.122/2002 vom 9. September 2003 E. 6.1.4 und 6.1.5 mit Hinweisen).
Die Festlegung der Höhe der Genugtuung beruht auf richterlichem Ermessen. Bei dessen Ausübung kommt den Besonderheiten des Einzelfalles entscheidendes Gewicht zu. Das schliesst allerdings nicht aus, dass sich das Gericht an Präjudizien orientiert, die nach Art und Schwere der beurteilten Verletzungen zum Vergleich geeignet sind. Aufgrund der Art und der Schwere der Verletzung ist zunächst die Grössenordnung der in Frage kommenden Genugtuung zu ermitteln. In einem zweiten Schritt sind die Besonderheiten des Einzelfalles, die eine Verminderung oder Erhöhung der zuzusprechenden Summe nahelegen, zu würdigen. Das Bundesgericht erachtet bei kürzeren Freiheitsentzügen Fr. 200.-- pro Tag als angemessene Genugtuung, sofern nicht aussergewöhnliche Umstände vorliegen, die eine höhere oder eine geringere Entschädigung zu rechtfertigen vermögen. Bei längerer Untersuchungshaft (von mehreren Monaten Dauer) ist der Tagessatz nach der dargelegten Praxis in der Regel zu senken, da die erste Haftzeit besonders erschwerend ins Gewicht fällt (vgl. <ref-ruling> E. 3b S. 156; Urteil 6B_745/2009 vom 12. November 2009 E. 7.1; Urteil 6C_2/2008 vom 24. März 2009 E. 2.3; Urteil 8G.122/2002 vom 9. September 2003 E. 6.1.6; je mit Hinweisen).
2.4 Gemäss <ref-law> kann die Anwendung einfachen kantonalen Rechts mit Beschwerde an das Bundesgericht nur gerügt werden, wenn geltend gemacht wird, sie verletze gleichzeitig das Willkürverbot von <ref-law>. Willkür liegt nach ständiger Rechtsprechung vor, wenn der Entscheid offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 1.3 S. 316; <ref-ruling> E. 4.2.1 S. 362; je mit Hinweisen). Dabei genügt es nicht, wenn der angefochtene Entscheid sich nur in der Begründung als unhaltbar erweist; eine Aufhebung des Entscheids rechtfertigt sich erst, wenn er auch im Ergebnis verfassungswidrig ist (<ref-ruling> E. 4.1 S. 133 mit Hinweisen).
2.5 Der Anspruch des Beschwerdegegners auf Genugtuung für erlittene Überhaft gemäss <ref-law>/ZH besteht nur für diejenigen Verfahrensabschnitte, in welchem ihm keine Kosten auferlegt werden (vgl. DONATSCH/SCHMID, Kommentar zur Strafprozessordnung des Kantons Zürich, N. 2 und 26 zu <ref-law>/ZH). Die Vorinstanz berücksichtigt bei der Kostenausscheidung, dass der Beschwerdegegner die Einleitung des Verfahrens durch sein verwerfliches Verhalten verursacht hat. Sie qualifiziert die Haft vom 30. Oktober 2007 bis zum 1. Februar 2008 als rechtmässig. In zutreffender Anwendung des kantonalen Prozessrechts legt sie dem Beschwerdegegner die bis zum 1. Februar 2008 anfallenden Kosten auf und verneint für diesen Verfahrensabschnitt den Anspruch auf Entschädigung. Eine Entschädigung für "Unbill der erstandenen Überhaft" behält sie jedoch ausdrücklich vor (angefochtenes Urteil E. V. 2 S. 13). Dieser Vorbehalt deutet darauf hin, dass die Vorinstanz die Genugtuung hypothetisch für die gesamte Dauer der Überhaft festgelegt und anschliessend den Betrag um das Mitverschulden des Beschwerdegegners herabgesetzt haben könnte. Dies ergibt sich aus den knappen vorinstanzlichen Erwägungen nicht, kann vorliegend aber offen gelassen werden. Denn der zugesprochene Genugtuungsbetrag von Fr. 45'000.-- fällt im Vergleich zur Rechtsprechung des Bundesgerichts zur Bemessung von Entschädigungen unhaltbar hoch und deshalb zumindest im Ergebnis willkürlich aus (vgl. Urteil 8G.122/2002 a.a.O. E. 6.1.4 mit zahlreichen Hinweisen). Nach Abzug der bis zum 1. Februar 2008 dauernden rechtmässigen Haft beträgt die Überhaft knapp 7 Monate. Dies ergibt einen Tagessatz von ungefähr Fr. 215.--. Dabei ist zu beachten, dass die Haft mehrere Monate dauerte, weshalb der Tagessatz mangels aussergewöhnlicher Umstände zu senken wäre. Zudem wiegen die vorgeworfenen Drohungen nicht derart schwer, dass sie besonders belastende Begleiterscheinungen der Haft und somit eine Erhöhung der Genugtuung begründen würden (vgl. Urteil 8G.122/2002 a.a.O. E. 6.1.8). Die Rüge der willkürlich festgesetzten Genugtuung erweist sich als begründet. Das angefochtene Urteil ist aufzuheben und die Sache zur neuen Bemessung der Genugtuung an die Vorinstanz zurückzuweisen.
3. Die Beschwerde ist gutzuheissen. Bei diesem Ausgang des Verfahrens ist der unterliegende Beschwerdegegner kostenpflichtig (<ref-law>). Sein Gesuch um unentgeltliche Rechtspflege und Verbeiständung kann indes gutgeheissen werden. Es sind daher keine Kosten zu erheben. Dem Rechtsvertreter des Beschwerdegegners ist aus der Bundesgerichtskasse eine angemessene Entschädigung auszurichten (<ref-law>). Der obsiegenden Beschwerdeführerin ist keine Entschädigung auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, das Urteil des Obergerichts des Kantons Zürich vom 31. Mai 2010 aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
2. Das Gesuch des Beschwerdegegners um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen.
3. Es werden keine Kosten erhoben.
4. Dem Rechtsvertreter des Beschwerdegegners, Rechtsanwalt Dr. iur. Valentin Landmann, wird für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 3'000.-- aus der Bundesgerichtskasse ausgerichtet.
5. Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 31. Januar 2011
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Favre Binz