Refal (conceived 1966, implemented 1968) is a language built upon the idea of structured pattern-matching.
A function definition is a sequence of constructs "pattern = replacement", operating on the function argument that consists of a sequence of terms.
Each term is either a symbol (a character or a meta-symbol like a number of a function ID), or a parenthesized sequence of terms.
A pattern is a similarly-structured sequence with free variables that can match individual symbols, terms or "expressions" (sequences of terms), as well as literal symbols.
A replacement is a sequence of terms with potential function call terms that use magic parentheses and the sequence in parentheses starts from a function ID.
The examples on the Wiki page, like
Fact { 0 = 1;
s.N = <* s.N <Fact <- s.N 1>>>; }
don't do the language justice; the main feature of the language is the ability to pattern-match structured data.
The language had a counter-culture popularity in the programming circles in the USSR after the author had to emigrate to the U.S. in 1977, and was taught by the author, Valentin Turchin, in the City College of New York until his death in 2010. Now, unfortunately, the reference links on the Refal wiki page are also dead.
Searching for "refal" on Github returned 1599 matches, though.