Рэнесанснаму замку Бехінэ папярэднічала сярэднявечная крэпасць, дакладны час узвядзення якой невядомы. Пра Бехінскую царкоўную правінцыю згадвае ў сваёй хроніцы яшчэ Казьма Пражскі (пам. 1125), аднак больш падрабязна гісторыя Бехінэ прасочваецца толькі з сярэдзіны XII стагоддзя, калі замка напэўна яшчэ не існавала.
Замак быў закладзены пры каралі Пржэмысле Отакары II, якія ўмацоўваў сваю ўладу на поўдні Чэхіі пасродкам заснавання шэрагу абарончых збудаванняў. У 1268 годзе кароль загадаў узвесці на гары Бехінэ замак, які павінен быў стаць яго апорным пунктам у супрацьстаянні з паўднёвачэшскім феадальным родам Віткавічаў. Аднак пасля смерці Пржэмысла Отакара II у 1278 годзе палітычны ўплыў караля на поўдні Чэхіі аслаб, а моц Віткавічаў (і асабліва іх галіны паноў з Рожмберка) істотна ўзрос.
У 1340 годзе кароль Ян Люксембургскі перадаў Бехінскае панства панам са Штэрнберка[1][2]. У 1398 годзе ўладальнікам панства і замка стаў мараўскі маркграф Ёшт Люксембургскі[2], ад якога ў 1405 годзе яны перайшлі ў валоданне Геральта з Кунштата[2]. У 1415 годзе[2] панства і замак сталі ўласнасцю Індржыха Лефла з Лажанаў. З тых часоў род Індржыха Лефла з Лажанаў насіў імя Бехіневы з Лажанаў. Індржых Лефл быў адным з першых прыхільнікаў вучэння Яна Гуса, аднак пазней перайшоў на бок караля Жыгімонта Люксембургскага.
