Sachverhalt:
A. X._ (geb. 1974) stammt aus Bosnien und Herzegowina. Er heiratete am 2. März 1996 seine Landsfrau Y._. Am 31. Mai 1996 wurde die gemeinsame Tochter Z._ geboren. 2002 ist die Ehe geschieden worden; das Amtsgericht in A._ sprach das Sorgerecht für Z._ der Mutter zu.
Am 2. Dezember 2007 heiratete X._ in Bosnien und Herzegowina die Schweizerin W._. Er reiste am 11. April 2008 in die Schweiz und erhielt infolge Familiennachzugs am 30. Mai 2008 eine Aufenthaltsbewilligung.
Am 27. Juli 2011 sprach das Amtsgericht in A._ X._ das Sorgerecht für Z._ zu. Die ehemalige Gattin führte in der Gerichtsverhandlung aus, die Interessen des Kindes seien bei der Zuteilung am wichtigsten; der Vater von Z._ stehe wirtschaftlich besser da und die Tochter pflege eine gute Beziehung zu ihrem Vater.
B. Im August 2011 stellte X._ ein Familiennachzugsgesuch für seine Tochter. Das Departement des Innern des Kantons Solothurn lehnte das Gesuch am 2. Dezember 2011 ab. Eine dagegen eingereichte Beschwerde ans Verwaltungsgericht des Kantons Solothurn blieb erfolglos.
C. Mit Eingabe vom 29. März 2012 beantragt X._, das Urteil des Verwaltungsgerichts des Kantons Solothurn vom 24. Februar 2012 aufzuheben. Der Familiennachzug zugunsten seiner Tochter sei zu bewilligen.
Das Departement des Innern und das Verwaltungsgericht des Kantons Solothurn sowie das Bundesamt für Migration beantragen, die Beschwerde abzuweisen.
Mit Verfügung vom 3. April 2012 hat das präsidierende Mitglied das Gesuch um aufschiebende Wirkung abgewiesen.

Erwägungen:
1. 1.1 Gemäss <ref-law> ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten unzulässig auf dem Gebiet des Ausländerrechts betreffend Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt.
1.2 Der Beschwerdeführer verfügt über eine Aufenthaltsbewilligung, nicht jedoch über eine Niederlassungsbewilligung. Er kann sich für den Nachzug seiner Tochter aus erster Ehe daher nicht auf Art. 43 Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (Ausländergesetz, AuG; SR 142.20) berufen. Obwohl seine jetzige Ehefrau Schweizer Bürgerin ist, kommt auch kein Anspruch nach Art. 42 Abs. 1 AuG in Betracht, weil sie nicht die Mutter der Tochter des Beschwerdeführers ist (vgl. zu Stiefkindern bzw. Stiefeltern: Urteil des Bundesgerichts 2C_537/2009 vom 31. März 2010 E. 2.2.2). Der Beschwerdeführer kann sich somit nur auf Art. 44 AuG stützen, der den Nachzug durch Ausländer mit Aufenthaltsbewilligung regelt (<ref-ruling> E. 1.2 S. 287 mit Hinweisen; Urteile 2C_888/2011 vom 20. Juni 2012 E. 2.4; 2C_793/2011 vom 22. Februar 2012 E. 1.1).
1.3 Art. 44 AuG räumt dem Beschwerdeführer, anders als Art. 42 und 43 AuG, keinen Nachzugsanspruch im Sinne von <ref-law> ein. Für den Nachzug seiner Tochter kann sich der Beschwerdeführer jedoch auf den Schutz des Familienlebens nach Art. 8 EMRK und <ref-law> berufen: Durch das Zusammenleben mit der Schweizer Ehefrau hat er selbst einen Anspruch auf Verlängerung seiner Aufenthaltsbewilligung nach Art. 42 Abs. 1 AuG und damit ein gefestigtes Anwesenheitsrecht. Zudem macht er eine intakte und tatsächlich gelebte Beziehung zu seiner Tochter geltend. Auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist deshalb einzutreten (<ref-law> e contrario). Ob der Familiennachzug letztlich zu gewähren ist, bildet Gegenstand der materiellen Beurteilung (<ref-ruling> E. 1.3 S. 287 mit Hinweisen).
1.4 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, wie die Vorinstanz ihn festgestellt hat (<ref-law>). Es kann diesen bloss berichtigen oder ergänzen, wenn er offensichtlich unrichtig oder in Verletzung wesentlicher Verfahrensrechte ermittelt worden ist (<ref-law>). Die betroffene Person muss rechtsgenügend dartun, dass und inwiefern der festgestellte Sachverhalt bzw. die beanstandete Beweiswürdigung klar und eindeutig mangelhaft erscheint (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG; vgl. <ref-ruling> E. 1.4.3; <ref-ruling> E. 1.3). Auf rein appellatorische Kritik an der Sachverhaltsermittlung und an der Beweiswürdigung tritt das Bundesgericht nicht ein (<ref-ruling> E. 3 S. 104 f.). Die Beschwerdeführer müssen - in Auseinandersetzung mit der Begründung im angefochtenen Entscheid - im Einzelnen dartun, inwiefern die Sachverhaltsfeststellung oder die Beweiswürdigung offensichtlich unhaltbar und damit willkürlich sein soll (vgl. <ref-ruling> E. 2.1 - 2.3).
2. Der Beschwerdeführer macht geltend, die Vorinstanz habe seinen Anspruch auf rechtliches Gehör und Art. 47 Abs. 4 AuG verletzt, indem sie seine Tochter nicht angehört habe.
2.1 Zum Anspruch auf rechtliches Gehör gehört das Recht des Betroffenen, sich vor Erlass eines in seine Rechtsstellung eingreifenden Entscheides zur Sache zu äussern sowie das Recht auf Abnahme der rechtzeitig und formrichtig angebotenen rechtserheblichen Beweismittel (<ref-ruling> E. 2b S. 56). Indessen räumt <ref-law> - entgegen der Auffassung des Beschwerdeführers - keinen Anspruch auf eine mündliche Anhörung ein (<ref-ruling> E. 2.1 S. 428 f.). Auch steht die Verfassungsgarantie einer vorweggenommenen Beweiswürdigung nicht entgegen. Das Gericht kann auf die Abnahme von Beweisen verzichten, wenn es aufgrund bereits abgenommener Beweise seine Überzeugung gebildet hat und ohne Willkür annehmen kann, seine Überzeugung werde durch weitere Beweiserhebungen nicht geändert (<ref-ruling> E. 5.3 S. 148; <ref-ruling> E. 2.1 S. 428; Urteil 2C_276/2011 vom 10. Oktober 2011 E. 2.1, nicht publ. in: <ref-ruling>).
2.2 Allerdings sind gemäss Art. 47 Abs. 4 AuG Kinder über 14 Jahren dann anzuhören, wenn dies erforderlich ist. Die Vorinstanz hat davon abgesehen, die Tochter des Beschwerdeführers anzuhören, weil sie dies aufgrund der vorliegenden Akten als entbehrlich erachtete. Dem ist nichts entgegenzuhalten: Der Beschwerdeführer hatte in den vorinstanzlichen Verfahren Gelegenheit, die Situation seiner Tochter umfassend darzulegen; sie selbst hatte in einem Brief an die Vorinstanz ihre Lebensumstände in Bosnien dargestellt und dabei das Gericht auch über ihren Wunsch in Kenntnis gesetzt, beim Vater zu leben. Ihre Ausführungen wurden von der Vorinstanz vollumfänglich in die Erwägungen miteinbezogen. Welche weiteren relevanten Ausführungen nur in einer Anhörung mit einem Dolmetscher noch hätten ermittelt werden können und müssen, ist nicht ersichtlich, sodass die Vorinstanz von einer solchen absehen durfte, ohne <ref-law> und Art. 47 Abs. 4 AuG zu verletzen. Weitere Rechte ergeben sich auch nicht aus dem vom Beschwerdeführer angerufenen Art. 12 der Kinderrechtskonvention (Übereinkommen vom 20. November 1989 über die Rechte des Kindes; SR 0.107; vgl. <ref-ruling> E. 3c S. 368, Urteile 2C_793/2011 vom 22. Februar 2012 E. 2.3; 2C_711/2011 vom 27. März 2012 E. 5.3; 2C_746/2009 vom 16. Juni 2010 E. 4).
3. 3.1 Die Tochter des Beschwerdeführers war bei Einreichung des Gesuchs um Familiennachzug bereits mehr als 15 Jahre alt. Sie wäre innerhalb eines Jahres nachzuziehen gewesen, nachdem der Beschwerdeführer im Mai 2008 über eine Aufenthaltsbewilligung verfügt hat (Art. 73 Abs. 1 und 2 VZAE [SR 142.201]; vgl. <ref-ruling> E. 3.3 S. 396 mit Hinweisen; Urteil 2C_888/2011 vom 20. Juni 2012 E. 2.4). Der Beschwerdeführer kann sich demnach nur auf wichtige familiäre Gründe berufen, die einen Familiennachzug auch dann zu rechtfertigen vermögen, wenn darum ausserhalb der gesetzlich vorgesehenen Fristen ersucht wird (Art. 47 Abs. 4 AuG; Urteil 2C_276/2011 vom 10. Oktober 2011 E. 4, nicht publ. in: <ref-ruling>).
3.2 Wichtige familiäre Gründe liegen unter anderem dann vor, wenn das Kindeswohl schwergewichtig nur durch einen Nachzug in die Schweiz sachgerecht gewahrt werden kann (vgl. <ref-law>). Entgegen dem Wortlaut dieser Verordnungsbestimmung ist dabei nach der Rechtsprechung jedoch nicht ausschliesslich auf das Kindeswohl abzustellen; es bedarf vielmehr einer Gesamtschau unter Berücksichtigung aller relevanten Elemente im Einzelfall. Dabei ist dem Sinn und Zweck der Fristenregelung Rechnung zu tragen, welche die Integration der Kinder erleichtern will, indem diese durch einen frühzeitigen Nachzug unter anderem auch eine möglichst umfassende Schulbildung in der Schweiz geniessen sollen. Zudem geht es darum, Nachzugsgesuchen entgegenzuwirken, die rechtsmissbräuchlich erst kurz vor Erreichen des erwerbstätigen Alters gestellt werden, wobei die erleichterte Zulassung zur Erwerbstätigkeit und nicht (mehr) die Bildung einer echten Familiengemeinschaft im Vordergrund steht (BBl 2002 3754 f. Ziff. 1.3.7.7). Die Bewilligung des Nachzugs nach Ablauf der Fristen hat nach dem Willen des Gesetzgebers die Ausnahme zu bleiben; dabei ist Art. 47 Abs. 4 Satz 1 AuG jeweils aber dennoch so zu handhaben, dass der Anspruch auf Schutz des Familienlebens nach Art. 8 EMRK bzw. <ref-law> nicht verletzt wird (Urteile 2C_780/2012 vom 3. September 2012 E. 2.2.; 2C_532/2012 vom 12. Juni 2012 E. 2.2; 2C_765/2011 vom 28. November 2011 E. 2.1; 2C_205/2011 vom 3. Oktober 2011 E. 4.2; 2C_709/2010 vom 25. Februar 2011 E. 5.1.1).
4. Wenn die kantonalen Behörden wichtige Gründe für einen "nachträglichen" Familiennachzug im Rahmen von Art. 47 Abs. 4 AuG abgelehnt haben, ist dies nicht zu beanstanden:
4.1 Der Beschwerdeführer macht geltend, die Vorinstanz habe den Sachverhalt hinsichtlich der Intensität der Kontakte des Vaters zu seiner Tochter offensichtlich falsch gewürdigt. So bestünde nicht lediglich in den Ferien ein Kontakt zu seiner Tochter, vielmehr habe er diese mehrere Male seit seiner Übersiedelung in die Schweiz besucht. Seine ehemalige Gattin lebe in einer neuen Beziehung und sei erneut Mutter geworden, weshalb sie sich nun nicht mehr um die gemeinsame Tochter kümmern könne.
4.2 Entgegen der Ansicht des Beschwerdeführers durfte die Vorinstanz davon ausgehen, die Tochter verfüge über eine engere Bindung zu ihrer Mutter als zu ihm, da sie seit mindestens 14 Jahren bei ihrer Mutter gelebt hat. Die Kontakte zum Beschwerdeführer waren demgegenüber wesentlich seltener und erfolgten per Telefon oder durch Besuche jeweils in den Ferien. Wenn der Beschwerdeführer unter Bezugnahme auf das Schreiben seiner Tochter darauf hinweist, die Beziehung seines Kindes zu ihrer Mutter sei sehr belastet, geht dies nicht aus dem Zuteilungsentscheid vom 27. Juli 2011 hervor, wo festgehalten wird, die Mutter stehe ihrem Kind sehr nahe und es falle ihr schwer, das Sorgerecht aus vorwiegend wirtschaftlichen Gründen zu übertragen. Soweit der Beschwerdeführer weiter geltend macht, ausser der Mutter nehme sich niemand seiner Tochter an, widerspricht dies seinen weiteren Ausführungen, wonach sich sowohl Nachbarn als auch die Grossmutter um sie gekümmert hätten, als es in der neuen Familie zu Spannungen gekommen sei. Ob alternative Unterbringungsmöglichkeiten in Bosnien evaluiert wurden, geht aus den Ausführungen des Beschwerdeführers nicht hervor und sein allgemeiner Hinweis, die Tochter könne sich nicht bis zur Mündigkeit bei ihrem Nachbarn oder bei weiteren Betreuungspersonen aufhalten, wird nicht weiter belegt, sodass das Bundesgericht an die Sachverhaltsermittlungen der Vorinstanz gebunden ist (vgl. E. 1.4).
Aufgrund der Akten durfte die Vorinstanz davon ausgehen, die Tochter des Beschwerdeführers verfüge über eine teilweise, ihrem Alter entsprechende Selbständigkeit, die es ihr erlaubt, unter Aufsicht und punktueller Betreuung durch ihre Verwandten und mit der finanziellen Hilfe des Beschwerdeführers von der Schweiz aus in ihrem Heimatland zu leben. Vor diesem Hintergrund kann der Vorinstanz nicht vorgeworfen werden, sie habe eine "prekäre Betreuungssituation" im Ausland ausser Acht gelassen. Mit ihren Ausführungen zur im Wesentlichen unsubstanziiert gebliebenen Betreuungssituation in Bosnien konnte die Vorinstanz auch <ref-law>, der den Schutz von sich in der Schweiz aufhaltenden Kindern und Jugendlichen regelt, nicht verletzen (dazu <ref-ruling> E. 5 d S. 390 ff.). Welche Rechte der Beschwerdeführer aus <ref-law> für sich und seine Tochter ableiten möchte, ist unklar und wird nicht weiter ausgeführt.
4.3 Wenn der Beschwerdeführer behauptet, der neue Partner seiner ehemaligen Frau gelte als aggressiv und sei dies auch mit seinem Kind, so weist die Vorinstanz zu Recht darauf hin, dass seine Tochter diese Behauptung in ihrem Schreiben an die Vorinstanz mit keinem Wort erwähnt hat. Entsprechende Hinweise auf eine Aggressivität ihr gegenüber ergeben sich auch nicht aus dem Sorgerechtsurteil, wo die Umteilung der Betreuungsverhältnisse detailliert begründet und dabei im Wesentlichen auf die besseren wirtschaftlichen Verhältnisse beim Beschwerdeführer abgestellt wird. Die Vorinstanz ist in zulässiger Weise zum Schluss gekommen, dass entsprechende Vorkommnisse blosse Behauptungen geblieben sind und die Tochter die Möglichkeit hatte, sich bei allfälligen Spannungen in der Familie mit dem neuen Partner ihrer Mutter und ihrer Halbschwester zu den Nachbarn oder weiteren Betreuungspersonen zu begeben. Eine untragbare Situation aufgrund der neuen Familiensituation ist nicht dargetan.
4.4 Der Beschwerdeführer bringt weiter vor, es wäre ihm rechtlich gar nicht möglich gewesen, seine Tochter vor dem Erlass des Sorgerechtsentscheids in die Schweiz nachzuziehen, weil bis dahin das Sorge- und Obhutsrecht alleine bei der Mutter lag. Aufgrund der veränderten familiären Situation läge es im Interesse des Kindeswohls, wenn die Tochter nunmehr von ihm betreut würde; dies entspräche schliesslich auch dem Wunsch seiner Tochter.
4.5 Entgegen der Ansicht des Beschwerdeführers lässt sich aus der Rechtsprechung, wonach dem um Nachzug der Kinder nachsuchenden Elternteil das Sorgerecht zukommen muss (<ref-ruling> E. 4.8 S. 86), nicht schliessen, die Fristen von <ref-law> würden generell erst mit der Übertragung des Sorgerechts zu laufen beginnen. Dem Beschwerdeführer war bekannt, dass für den Familiennachzug in die Schweiz Fristen bestehen (Beschwerde, S. 4). Er hat zu jenem Zeitpunkt seine Tochter bewusst in Bosnien bei seiner ehemaligen Gattin zurückgelassen und damit akzeptiert, die entsprechenden familiären Beziehungen künftig nur besuchsweise und damit eingeschränkt leben zu können; dies schloss auch Entwicklungen wie die erneute Familiengründung durch seine ehemalige Gattin mit ein.
Die Tochter des Beschwerdeführers hat ihrerseits die Sozialisierung und Schulausbildung in Bosnien und Herzegowina durchlaufen. Sie verfügt mit Ausnahme ihrer Beziehung zum Beschwerdeführer über keinerlei Bindungen in die Schweiz und spricht keine Landessprache in dem Mass, dass sie sich hier verständigen könnte; eine Integration in die hiesigen Verhältnisse dürfte ihr schwerfallen. Es sind somit keine stichhaltigen Gründe ersichtlich, weshalb die Tochter nach Abschluss ihrer Schulausbildung, in einem Alter, das ihr erlaubt, mit eingeschränkter Betreuung selbstständig in der ihr vertrauten Umgebung zu leben, kurz vor Eintritt in den Arbeitsmarkt noch in die Schweiz nachgezogen werden soll. Der Beschwerdeführer hatte sich während mehrerer Jahre, als seine Tochter noch kleiner war, nicht hierum bemüht (vgl. die Urteile 2C_780/2012 vom 3. September 2012 E. 2.3.2; 2C_888/2011 vom 20. Juni 2012 E. 3.2 und 2C_506/2012 vom 12. Juni 2012 E. 2).
5. 5.1 Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Der angefochtene Entscheid verletzt weder nationales noch internationales Recht (vgl. Art. 8 Ziff. 2 EMRK).
5.2 Der unterliegende Beschwerdeführer hat die Kosten für das bundesgerichtliche Verfahren zu tragen (vgl. <ref-law>). Es sind keine Parteientschädigungen geschuldet (vgl. <ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Solothurn und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 1. Oktober 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Hänni