Vom Namen Königsheim ausgehend ist anzunehmen, dass der Ort einmal Königsgut war und vermutlich in der Zeit der fränkischen Landnahme (7./8. Jh.) gegründet wurde. Urkundlich taucht der Name aber erstmals im 13. Jh. auf. In einer – gefälschten – Urkunde 1253 wird Königsheim als Besitz des Klosters Beuron erwähnt, dessen Vogtei durch das Dokument an den Zollergrafen in Mühlheim überging. Dieser verpfändete seinen Besitz 1303 an das Bistum Konstanz, und bei diesem (echten) Akt ist das dorf zi Kungeshain mit lute, mit gut, mit gerihte erneut als beuronisches Gut genannt. Als Bestandteil eines zu Beuron gehörenden Besitzkomplexes stand Königsheim damals in der Verfügung des Mühlheimer Stadtherren.

Die Hohenzollern mussten ihre Herrschaft Mühlheim 1391 an die Ritter von Weitingen verkaufen, wodurch Mühlheim, die Burg Bronnen mit Rechten in Kolbingen, Beuron, Irndorf, Buchheim und Worndorf und die Ortschaften Stetten, Nendingen, Königsheim (Küngshain), Böttingen und Mahlstetten einen neuen Herrn erhielten. Von den Weitingen ging der Besitzkomplex 1409 an das Haus Enzberg über. Die Mühlheimer Herrschaft umfasste durch die Jahrhunderte mit den drei Heuberggemeinden Königsheim, Böttingen und Mahlstetten die Stadt Mühlheim, Stetten, Nendingen, Irndorf, Buchheim und Worndorf. Allerdings war der genaue Umfang der enzbergischen Rechte häufiger Konfliktstoff mit dem Haus Habsburg als Inhaber der benachbarten Grafschaft Hohenberg.

Königsheim als flächenmäßig kleinste Gemeinde auf dem Heuberg bot sechs bis zwölf Bauernfamilien ein Einkommen aus der Landwirtschaft. Die meisten dieser Lehenhöfe waren im Besitz der Grundherrschaft, also des Hauses Enzberg, nur eine bis zwei Bauernstellen gehörten der Kirchengemeinde. Die Mehrheit der Familien hatte jedoch keine Lehen inne und musste den Lebensunterhalt als Taglöhner bei den Bauern, aus einer handwerklichen Tätigkeit oder aus einer kleinen Landwirtschaft auf eigenem Boden erwirtschaften.

1805 fiel Königsheim mit der Herrschaft Mühlheim an das Königreich Württemberg und wurde dem Oberamt Spaichingen zugeordnet. Neben zwölf Bauern arbeiteten 1825 in Königsheim fünf Leinweber, zwei Schuster, sieben Maurer, je ein Knopfmacher und Wagner, zwei Zimmerleute, zwei Schmiede, vier Händler und drei Wirtschaften. Die meisten Handwerker waren als Wanderarbeiter tätig; sie arbeiteten meist auswärts, wo immer sich Arbeit fand. Bis ins 20. Jh. hinein verbrachten viele Königsheimer Handwerker nur den Winter daheim und arbeiteten das Jahr über auf Baustellen von der Schweiz über das Rheinland bis nach Bayern. Der Armut in der Heimat entflohen bereits im 18. Jh. viele Familien, die in die Donauländer und nach Amerika auswanderten.

Seit der Auflösung des Oberamts Spaichingen im Jahr 1938 gehört Königsheim dem Landkreis Tuttlingen an und bildet seit der Gemeindereform der 70er Jahre eine Gemeinde des Verwaltungsverbandes Heuberg. Nach dem Krieg nahm der Ort einen steilen wirtschaftlichen Aufstieg. Insbesondere seit den 1950er Jahren entstand eine starke metallverarbeitende Industrie, so dass die Gemeinde heute mehr Arbeitsplätze als Berufstätige hat. In Königsheim leben ca. 560 Menschen.