Sachverhalt: A. Mit Schreiben vom 14. März 2008 ersuchte der designierte Co-Klinikdirektor Dr. phil. Z._ das Departement des Innern des Kantons Solothurn, vertreten durch das Gesundheitsamt, um Erteilung einer Betriebsbewilligung für die Klinik KK._ in A._. Das ursprünglich eingereichte Betriebskonzept wurde nach einer Besichtigung und diversen Besprechungen mehrmals überarbeitet. Die letzte Fassung des Betriebskonzepts für die inzwischen umbenannte Klinik K._, Privatklinik für psychische Gesundheit und Rehabilitation AG in Gründung wurde dem Gesundheitsamt am 29. Juni 2009 eingereicht. Als Verwaltungsratspräsident war gemäss Konzept und Gründungsakten Y._ vorgesehen; als weitere Verwaltungsräte sollten die beiden designierten Co-Klinikdirektoren Dr. phil. Z._ sowie Dr. med. X._ fungieren. B. Am 12. August 2009 wies das Departement des Innern des Kantons Solothurn das Gesuch um Erteilung einer Betriebsbewilligung für ein Privatspital ab. Es führte aus, das medizinische Untersuchungs- und Behandlungsangebot der Gesuchstellerin entspreche nicht den gesetzlichen Anforderungen an ein Spital. Das geplante Vorhaben bedürfe keiner Spitalbewilligung; dessen Umsetzung könne mit einer Betriebsbewilligung für eine ambulante Institution oder mit persönlichen Berufsausübungsbewilligungen erreicht werden. Eine von der Klinik K._ AG (in Gründung) bzw. Dr. med. X._ dagegen eingereichte Beschwerde wies das Verwaltungsgericht des Kantons Solothurn mit Urteil vom 5. Februar 2010 ab. C. Mit Eingabe vom 10. März 2010 erheben die Klinik K._ AG (in Gründung), Dr. med. X._ und Y._ Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Sie beantragen, das Urteil des Verwaltungsgerichts vom 5. Februar 2010 sei aufzuheben und die Vorinstanz sei anzuweisen, die Bewilligungsverweigerung aufzuheben. Eventualiter sei die Sache zur Erhebung des rechtserheblichen Sachverhalts an die Vorinstanz zurückzuweisen. D. Das Verwaltungsgericht des Kantons Solothurn beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Departement des Innern des Kantons Solothurn, vertreten durch das Gesundheitsamt, schliesst auf Abweisung der Beschwerde.