Sachverhalt: A. Der mazedonische Staatsangehörige X._ (geb. 1985) heiratete am 13. April 2005 in seiner Heimat die in der Schweiz geborene und niedergelassene serbische Staatsangehörige Y._ (geb. 1988). Am 24. Oktober 2005 reiste er in die Schweiz ein und erhielt eine Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau. Im Mai 2007 kam die gemeinsame Tochter Z._ zur Welt. Mit Eheschutzverfügung vom 23. Juni 2008 stellte das Richteramt A._ fest, dass die Ehegatten seit dem 23. April 2008 getrennt lebten. Per 1. Juli 2009 nahmen die Eheleute die Haushaltsgemeinschaft wieder auf, worauf die Migrationsbehörde des Kantons Solothurn mit Verfügung vom 22. Juli 2009 die Aufenthaltsbewilligung von X._ verlängerte. Im Dezember 2009 kam es zur erneuten Trennung der Eheleute. Mit Urteil vom 19. Mai 2011 des Richteramtes A._ wurde die Ehe auf Antrag beider Parteien geschieden und die elterliche Sorge über die Tochter Z._ der Mutter zugeteilt. B. Am 30. Mai 2011 verfügte die Migrationsbehörde, dass die Aufenthaltsbewilligung von X._ nicht verlängert werde und dieser die Schweiz bis zum 31. August 2011 zu verlassen habe. Die dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Solothurn mit Urteil vom 4. November 2011 ab und forderte X._ auf, die Schweiz bis zum 31. Januar 2012 zu verlassen. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 8. Dezember 2011 beantragt X._, das Urteil des Verwaltungsgerichts des Kantons Solothurn vom 4. November 2011 sei aufzuheben und seine Aufenthaltsbewilligung sei zu verlängern. Gerügt wird die Verletzung von Bundesrecht sowie von Art. 13 BV bzw. Art. 8 EMRK. D. Das Verwaltungsgericht und die Migrationsbehörde des Kantons Solothurn beantragen, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Das Bundesamt für Migration schliesst auf Abweisung der Beschwerde. Mit Verfügung vom 13. Dezember 2011 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.