築城年代は定かではないが行松氏によって築かれたと云われる。
大永4年(1524年)尼子氏によって攻められ落城し行松氏は逃れた。 永録5年(1562年)毛利氏が尼子氏の白鹿城を攻撃した頃、行松氏も当城を回復した。
行松正盛が病死すると毛利氏の部将杉原盛重が入城し八橋城と共に羽衣石城南条氏の押えとした。杉原盛重が没すると嫡男元盛が家督を継いだが、その弟景盛によって謀殺され、景盛もまた毛利によって滅ぼされた。
関ヶ原合戦後、伯耆一国の領主となった中村一忠は当時築城中であった米子城が完成するまでの間、当城に留まり、完成とともに廃城となった。
尾高城は比高20m程の台地の西端に築かれている。西へ突き出した台地の先端で、北、西、南の三方は崖地になっており、東のみ地続きとなる。この台地に大きな空堀と土塁で区画した曲輪群を配しているのが特徴で、この辺りでは少ないが、関東や長野などでは多く見かける選地と縄張りである。
現在公園として良く整備されているのが、「南大首」、「中の丸」と呼ばれる曲輪で土塁や空堀が良く残る。中丸の西にあり整備されていない部分に本丸、その先に二の丸がある。道路の南側「シャトー・おだか」のある所が「天神丸」である。