1856 wurde die Brauerei mit einem Stammkapital von 300.000 Talern als Aktiengesellschaft von einflussreichen Dresdner Bankiers, Industriellen und Politikern gegründet. Gegen deren Bau hatte sich bis zuletzt die Dresdner Brauerinnung gestellt, welche Umsatzeinbußen durch den modernen Großbetrieb befürchtete. Erst ein Gutachten der Kreisdirektion vom 26. September 1856 lehnte den Einspruch der ab und ermöglichte den Beginn der Bauarbeiten. Am 15. April 1857 erfolgte im Beisein König Johanns die offizielle Grundsteinlegung für die Produktionsgebäude. Mit der Eröffnung der Restauration "Zum Felsenkeller" am 10. November 1858 war der Aufbau der Brauerei endgültig abgeschlossen.

Eine Besonderheit stellten die neun in den harten Syenitfelsen getriebenen Lagerkeller dar, welche je ca. 66m lang und 6m im Durchmesser und durch einen 140m langen Gang miteinander verbunden sind. Die Kosten für den Lagerkellerbau hatten sich mit 59.000 Talern mehr als verdoppelt und die Bauzeit mit 15 Monaten mehr als verfünffacht.

Das Unternehmen wuchs schnell und entwickelte sich bis 1900 zur bedeutendsten sächsischen Großbrauerei. Zu den Kuriositäten aus der Frühzeit des Unternehmens gehört die von einigen Aktionären 1862 verbreitete Legende vom “Eiswurm”, der in den Kühlkellern der Brauerei hausen sollte und so das hier gelagerte Bier verderben würde. In Panik verkauften mehrere Kleinaktionäre ihre Anteile, so dass sich das Kapital nun in wenigen Händen konzentrierte. Der Wurm wurde in Form eines roten Drachens später Markenzeichen der Brauerei und war auch Namenspatron der Straße Am Eiswurmlager hinter der Brauerei.

Die Felsenkellerbrauerei stellte zunächst bayrisches Lagerbier, ab 1880 vorrangig Bier nach Pilsner Brauart her und war wirtschaftlich äußerst erfolgreich. Moderne Anlagen ermöglichten in der zwischen 1871 und 1895 mehrmals erweiterten Brauerei eine effektive Produktion. Gegenüber den eigentlichen Braugebäuden entstand um 1890 ein Gebäudekomplex für den umfangreichen Fuhrpark. Außerdem richtete man an Stelle der früheren Villa Grassi eine Brauereigaststätte mit großem Saal ein, die sich zum beliebten Ausflugsziel der Dresdner entwickelte. Dieses Gebäude wurde 1945 durch Bomben schwer beschädigt und 1957 als Kulturhaus Felsenkeller wieder eröffnet.

1946 wurde die Felsenkeller AG aufgelöst und der Betrieb als VVB Brau- und Malzindustrie in Volkseigentum überführt. Trotz schwieriger Bedingungen gelang es, den Braubetrieb fortzusetzen und den jährlichen Ausstoß bis 1973 auf ca. 500.000 Hektoliter zu erhöhen. Im Zusammenhang mit dem Konzentrationsprozess der Dresdner Brauereien wurde in den 60er Jahren der Betriebsteil Freital-Döhlen an die Felsenkellerbrauerei angeschlossen und diese selbst 1978 in das VEB Getränkekombinat Dresden eingegliedert. Nach Fertigstellung der modernen Großbrauerei in Coschütz 1981 stellte die Felsenkellerbrauerei die Flaschenbierproduktion ein und produzierte nun nur noch Fassbier. 1990 wurde die Brauerei ganz geschlossen.

Ein Grossteil der Gebäude ist noch vorhanden.