Предпологают, что на Виллимяги существовало городище древних эстов. После вторжения крестоносцев близлежащие земли перешли во владение Ордена меченосцев (позднее – Ливонского ордена). Владения были закреплены за орденом Стенбийским договором (1238), наложившим запрет на строительство укреплений в Ярвамаа. Однако в 1260 году Орден построил замок прямо на границе древнего Ярвамаа. Название свое крепость завоевателей получила от местного известняка (по-эстонски Паэде, посже – Пайде, по немецки Виттенштейн, Вейсенштейн – белый камень). Поселение вокруг замка в 1291 году получило от Ордена права города. Замок укреплялся в XIV веке и в начале XV века. Во второй половине XVI века для защиты от огнестрельного оружия были построены бастионы и окружающий обводную стену земляной вал (в настоящее время это дорога вокруг Виллимяги).
Во время Ливонской войны русские войска в 1560 году осадили замок, но взять его не смогли и только после второй осады (1572-1573) он был захвачен войсками Ивана IV . Восемь лет спустя Пайде сдался шведским войскам.
Последовала борьба за крепость между Польшей и Швецией. В 1602 году Пайде захватили польские, а в 1608 году – вновь шведские войска. В ходе этого Пайдеский замок и город сильно постродали. В 1638 году Пайде был исключен из списка крепостей, поселение же подчинили Мяоской мызе, и оно потеряло права города.