Wie die Orchester-Serenade Nr. 1 op. 11 entstand auch das Gegenstück op. 16 in der kleinen Fürstenresidenz Detmold in den Sommern von 1858 und 1859. Brahms, damals etwa Mitte zwanzig, genoß die Sommer im Dienste der fürstlichen Familie, was auch diese Werke von filigraner Leichtigkeit und fröhlicher Beschwingtheit widerspiegeln. Die beiden Kompositionen sind so sanft, so bescheiden im Klangvolumen, so zart und von solch idyllischer Stimmung, daß sie als bewußte Reaktion auf die Monumentalität des unmittelbaren Vorgängerwerkes, des Ersten Klavierkonzerts d-Moll op. 15 erscheinen.

Brahms drückte seine Freude über die Serenade Nr. 2 mit folgenden Worten aus: "Mir war ganz wonniglich dabei zu Mute. Mit solcher Lust habe ich selten Noten geschrieben, die Töne drangen so liebevoll und weich in mich, daß ich durch und durch heiter war." Die Uraufführung fand am 10. Februar 1860 in Hamburg statt.

Anläßlich des 150. Geburtstages von Johannes Brahms im Jahre 1983 nahm Leonard Bernstein mit den Wiener Philharmonikern zwischen 1981 und 1984 fast alle Orchesterwerke des Komponisten für Schallplatte und Video auf. Heute gilt dieser Zyklus als Meilenstein in der Interpretation der Musik von Johannes Brahms. Für Bernstein war Brahms "ein wahrer Romantiker, der seine Leidenschaften in ein klassisches Gewand kleidete", aber auch "ein norddeutscher Klassiker, den es nach Wien verschlagen hatte und der sich dort von Donau, Karpaten und dem Temperament der Zigeuner hatte inspirieren lassen". Bernstein und die Wiener Philharmoniker berücksichtigten diesen Dualismus und unterstrichen sowohl das klassische als auch das romantische Element, die dramatische Intensität und die nüchterne Zurückhaltung von Brahms' Musik.

Die Konzerte fanden im Goldenen Saal des Wiener Musikvereins statt, dem Uraufführungsort von zwei Brahms-Symphonien, wo auch der Komponist selbst schon dirigiert hatte.