Take Black IPA. When was the first one brewed? 2008? 2003? 1995? Perhaps a little earlier.
The possibility of using such material turns upon the fact that a large proportion of the malt used consists of highly caramelised varieties, and, as before explained, caramelised bodies possess a marked preservative or antiseptic character, while the black beers produced are not always required to keep for any very lengthy period. To begin with, then, it is not customary to employ saline waters, or, in other words, if such water be employed the black beer produced is deficient in that roundness and fulness of palate taste that is considered so necessary a feature, while I can example this by referring to the black beer produced at Burton, which has been universally described as a mere black pale ale—i.e., though black in colour, its palate taste reminds one very strongly of the pale beers produced by Burton firms. It will be quite understood that I am not decrying this article; it may and does suit many palate tastes, and is thought a great deal of on the Continent, but at the same time it differs very widely from the accepted standard quality of a black beer as specified."
"The theory and practice of modern brewing" by Frank Faulkner, 1888, pages 259-260.
At least 1888. Black Pale Ale existed at least by then.
Innovation my arse.
Thanks again Gary for the Google books link.