Sohn des Stadtzimmermeisters Josef Fellner (ca. 1770–1843) und der Anna Maria Fellner, geb. Reister (ca. 1779–1831), Bruder des Hofzimmermeisters Jacob Fellner (1809–1871), Vater von →Ferdinand II. Fellner, Großvater von →Ferdinand III. Fellner; ab 1846 verheiratet mit Caroline Perl (1828–1895); acht Kinder. – F. absolvierte 1829–35 ein Architekturstudium am polytechnischen Institut in Wien, besuchte 1834–37 die Akademie der bildenden Künste bei →Peter Nobile (1835 Gundel-Preis) und unternahm 1837–39 eine Studienreise, die ihn auch nach Italien führte. Ab 1848 war F. in Wien als selbstständiger Architekt tätig und avancierte zu einem der führenden Spezialisten im öffentlichen Nutz- und Kommunalbau (z. B. Realschulgebäude, 1853–55, Wien 4; Bürgerversorgungshaus, 1858–60, Wien 9, nicht erhalten). Außerdem errichtete er Wohn- und Geschäftshäuser sowie Palais in Wien (z. B. Haus Liebig, 1857–58, Palais Philipp, 1861, beide Wien 1). F. gestaltete die Mietshäuser besonders repräsentativ, um deren Bedeutung als beste Wohnform im Großstadtbereich zu betonen. Er reagierte damit auf Forderungen von →Heinrich Freiherr von Ferstel und →Rudolf von Eitelberger-Edelberg, die auch in der Großstadt den Bau von Einfamilienhäusern propagierten. Weiters errichtete er eine Reihe von Interimstheatern, die aus Holz gefertigt wurden und daher meist bald Bränden zum Opfer fielen (Thaliatheater, 1856, Wien 16). Als er den wichtigen Auftrag zur Errichtung des Wiener Stadttheaters (1871–72, Wien 1) erhielt, war er bereits schwer herzkrank und auf die Mitarbeit seines erst 19-jährigen Sohns Ferdinand angewiesen, der das Gebäude nach dem wenig später erfolgtem Tod des Vaters vollendete. Obwohl aus Stein gebaut, brannte es zwölf Jahre später ab und wurde von Ferdinand II. Fellner mit seinem Ateliermitarbeiter →Hermann Helmer als Konzert- und Ballhaus Etablissement Ronacher wieder errichtet. F. gilt als Vertreter des romantischen Historismus. Er lehnte die nüchterne, zweckmäßige Bauweise der ersten Jahrhunderthälfte ab und belebte die Fassaden durch plastische Formulierungen und malerischen, reichen Dekor. Er griff nach wie vor spätklassizistische Formulierungen auf, ergänzte diese jedoch mit byzantinischem und mittelalterlichem Vokabular (Handelsakademie, 1860–62, Wien 1). F. war 1861–62 und 1868–70 Gemeinderat des Bezirks Roßau, ab 1848 w. Mitglied der Akademie der bildenden Künste, Mitglied des Niederösterreichischen Gewerbevereins und Verwaltungsrat der Wiener Baugesellschaft.