El mismo nombre de «Bastei» [bastión] indica la inclusión de las empinadas e imponentes rocas en el antiguo anillo defensivo alrededor del castillo de Neurathen. En 1592 la roca fue mencionada por primera vez por Matthias Oeder en el curso de la primera encuesta estatal por el electorado de Sajonia como Pastey. Cuando la región de la Suiza sajona fue explorada y se desarrolló turísticamente, las rocas Bastei se convirtieron en una de sus primeras atracciones. Su mirador fue mencionado por primera vez en la literatura de viajes en 1798 en una publicación de Christian August Eberhard Gottlob. Una de las primeras guías de senderismo que atrajo visitantes a Bastei fue la Carl Heinrich Nicolai, quien escribió en 1801:

El Bastei tiene un acceso relativamente fácil solo desde Wehlen y Lohmen. Numerosos artistas llegaron al Bastei por el llamado camino del pintor, el Malerweg. Caspar David Friedrich pintó su famoso cuadro Felsenpartie im Elbsandsteingebirge [Rocas en las montañas de arenisca del Elba] inspirándose en el Bastei. Ludwig Richter también hizo apuntes en el Bastei. Desde Rathen, el acceso solía ser más difícil, pero en 1814 se colocó una escalera con 487 escalones que salía del valle Wehlgrund más allá del Vogeltelle y ascendía hasta las rocas.

En Pentecostés de 1812, el carnicero de Lohmen, Pietzsch, inició los primeros servicios de aprovisionamiento para los visitantes del Bastei. Desde dos sencillas cabañas vendía pan, mantequilla, cerveza, aguardiente, café y leche. Dos años más tarde, construyó una cocina y una bodega bajo uno de los salientes de roca y el mirador fue equipado con una barandilla. En febrero de 1816, a Pietzsch se le otorgó una licencia para vender bebidas alcohólicas; por desgracia, las modestas cabañas que había construido se destruyeron en un incendio en septiembre de ese mismo año. En junio de 1819, August von Goethe informó: «chozas amables y un buen servicio con café, cerveza doble, licores y pan fresco y mantequilla realmente revivieron al cansado vagabundo...».[2]​ En 1820, la licencia alcohólica fue al juez de Rathen (Erblehnrichter), Schedlich.

El desarrollo del Bastei recibió un importante impulso en 1826. Ese año, se erigió el primer edificio sólido para el alojamiento durante la noche, basándose en los planos de Gottlob Friedrich Thormeyer. Desde ese momento las viejas chozas sirvieron como cuartos noche para los guías de senderismo. El primer puente, llamado Puente de Bastei (Basteibrücke), fue construido en madera sobre las profundas hendiduras del Mardertelle, que une la plataforma exterior de la roca Bastei con las rocas Steinschleuder y Neurathener Felsentor. En 1851, debido al aumento constante de visitantes, el puente de madera fue reemplazado por un puente de piedra arenisca que sigue en pie hoy en día. Tiene 76,5 m de longitud y los siete arcos salvan un barranco de 40 metros de profundidad, conocido como el Mardertelle.

A finales del siglo XIX, el Bastei se convirtió finalmente en la principal atracción de la Suiza sajona. La posada existente fue completamente acondicionada y ampliada en 1893/94. Un abastecimiento de agua de alta presión se dispuso en 1895 y una línea de teléfono en 1897. Alrededor de 1900, se planeó la construcción de un ferrocarril de montaña desde el valle del Elba al Bastei, pero no llegó a buen término. Incluso hoy en día un barranco al suroeste del Bastei se conoce como el Eisenbahngründel ["Pequeño Ferrocarril del Valle"]. A principios del siglo XX, la carretera a Bastei se amplió para manejar la creciente motorización.

Después de 1945 el número de visitantes volvió a aumentar bruscamente, ante todo los fines de semana y días festivos, ya que el Bastei se convirtió en un lugar de turismo masivo. Entre 1975 y 1979 la antigua posada fue sustituida por un nuevo edificio más grande, más tarde, un hotel.