Sachverhalt: A. A._ (Serbe; 1980) heiratete am 13. September 2006 eine in der Schweiz niederlassungsberechtigte Ausländerin (1979), weshalb er in der Folge eine Aufenthaltsbewilligung erhielt. Am 14. Januar 2007wurde der gemeinsame Haushalt aufgehoben; in der Zwischenzeit sind die Eheleute geschieden. Die gemeinsame Tochter wurde am 3. August 2007 geboren. Mit Verfügung vom 3. August 2008 wurde die Aufenthaltsbewilligung von A._ nicht mehr verlängert und er wurde per 4. September 2009 aus der Schweiz weggewiesen. Die Rechtsmittel dagegen waren erfolglos. B. Am 10. August 2015 verheiratete sich A._ in Serbien mit der deutschen Staatsangehörigen B._ (1962), welche über eine Aufenthaltsbewilligung in der Schweiz verfügt. Trotz des Verdachts auf eine Scheinehe erteilte die Migrationsbehörde ihm eine Aufenthaltsbewilligung (18. November 2016). Am 24. August 2017 besuchte die Kantonspolizei die Wohnung der Eheleute. Gestützt darauf widerrief die Migrationsbehörde des Kantons Solothurn am 20. März 2018 die Aufenthaltsbewilligung von A._. Die Beschwerde dagegen war vor dem Verwaltungsgericht des Kantons Solothurn erfolglos (Urteil vom 24. Oktober 2018). C. Vor Bundesgericht beantragt A._, das Urteil des Verwaltungsgerichts des Kantons Solothurn vom 24. Oktober 2018 und den Widerruf seiner Aufenthaltsbewilligung aufzuheben. Zudem beantragt er unentgeltliche Rechtspflege. Das Verwaltungsgericht und das Migrationsamt des Kantons Solothurn beantragen unter Verzicht einer Vernehmlassung die Abweisung der Beschwerde. Mit Verfügung vom 27. November 2018 hat der Präsident der II. öffentlich-rechtlichen Abeilung der Beschwerde aufschiebende Wirkung zuerkannt.