Сама назва Бастай (бастіон) вказує на те, що ці високі скелі використовувались як оборонне кільце навколо старовинного скельного замку Нойратен[de]. Бастай згадується вперше в 1592 році Матіасом Оадером у першому та найповнішому, для свого часу, землемірному картографічному дослідженні, яке було виконане на замовлення саксонського курфюрста. Завдяки своїй неповторній красі та казковій мальовничості Бастай став відомим туристичним місцем. В довідниках для подорожей він згадується у 1798 році. Відомий німецький вчитель, теолог та письменник Карл Генріх Ніколаі писав: «Які високі почуття наповнюють душу! Можна стояти довгий час, нескінченно… важко відірватися від цього місця». Краса Бастаю надихала багатьох творчих особистостей. Численні художники відвідували Бастай, створивши так званий Шлях Художника. Серед них Каспар Давид Фрідріх, що написав картинку «Скелі піщаних гір Ельби» та Людвіг Ріхтер. Відомий російський композитор та піаніст Олександр Скрябін під час своїх гастролей у Німеччині двічі відвідував Бастай. Під враженнями ним була створена однойменна прелюдія «Бастай».

У 1812 році з двох простих хатин почалися перші послуги громадського харчування для відвідувачів Бастаю. Значний розвиток Бастаю як туристичного місця почався 1826 року коли був побудований готель. Наприкінці 19 століття захоплюючий, величний і чаруючий своєю неповторністю Бастай перетворився на одну з головних пам'яток Саксонської Швейцарії, якою є і досі.