「小国」というのは、出雲の大本宮に対する遠江の美称であるという。また、古くは許当麻知〔ことまち〕神社(願い事を待つの意)、事任〔ことのまま〕神社(願い事のままに叶うという意)とも称されたという。
創建については不祥だが、社記によれば、欽明天皇16年(555)2月18日、本宮山の頂上に鎮斎され、その後、現社地に社殿が造営されたとされる。以来、朝廷より勅使が送られ、大宝元年(701)の奉幣の際には十二段の舞楽が奉奏されたという。
文献上に初めて現れるのは承和7年(840)で、『続日本後紀』6月24日条に周智郡の小国天神と磐田郡の矢奈比売天神に従五位下が授けられたとある。延喜の制では小社に列している。
元亀3年(1572)一宮荘の代官であった武藤刑部丞氏定が武田信玄と結び、甲斐の兵を招き入れて小国神社に立て籠もった。しかし、神主の小国豊前重勝は武田方につくことを拒み、徳川方についた。徳川家康は小国重勝に命じて御神霊を別所に遷し、願文と三条小鍛治宗近作の太刀を奉納して戦勝を祈願した後、社殿に火を放たせしめた。そして天正3年(1575)武田軍に勝利すると、社殿を再建し、御神霊を復座した。
このことにより、徳川氏は小国神社を篤く崇敬し、家康は朱印領590石を寄進している。また、以後も徳川将軍家により社殿の改造・修復が行われた。
明治6年(1873)国幣小社に昇格。明治15年(1882)火災により社殿が全焼。同19年(1886)再建された。