1240 wird Mülenen erstmals als Moledino erwähnt, erste nachweisbare Besitzer sind die Freiherren von Kien. Burg und Städtchen sind Bestandteil der Herrschaft Mülenen-Aeschi. Als 1400 Bern die Herrschaft Frutigen kauft und die Tellenburg ausbaut, verfällt die Burg Mülenen. Ein Turm wird noch als Gefängnis benutzt. 1887 beschreibt Pfarrer Stettler die damals noch vorhandene Anlage so: «Ein torähnliches, massives Gebäude mit einer hinten anschliessenden Mauer verrät die versunkene Herrlichkeit des Ortes. Die Mauer verband wohl da Tor mit dem Schloss, das auf dem anstossenden Hügel stand, und ein teilweise jetzt noch sichtbarer Damm mit einer Mauer zog sch rechter Hand als schützende Letzi quer durch das hier enge Tal.»

Diese Letzimauer ist beim Bau der Umfahrungsstrasse wieder entdeckt worden und ist heute teilweise offen sichtbar. Die Armee nutzte diese erwähnte enge Stelle im Zweiten Weltkrieg ebenfalls und baute dort mehrere Bunker und eine massive Sperrstelle.