1991/92 entwickelte sich eine Diskussion über eine eigene Auszeichnung für Soldaten, die in Auslandseinsätze entsandt wurden. Die ersten NATO-Einsätze im Rahmen des Zweiten Golfkrieges waren gerade abgeschlossen worden, der UN-Einsatz in Kambodscha angelaufen.
Von der UN oder der NATO verliehene Auszeichnungen durften Bundeswehrangehörige zunächst aus ordensrechtlichen Gründen nicht ohne Weiteres tragen. Außerdem wünschten sich die aus den Einsätzen zurückkehrenden Soldaten eine eigene, nationale Auszeichnung, wie sie in den Streitkräften verbündeter Staaten üblich war. Das Bundesministerium der Verteidigung (BMVg) reagierte hierauf und begann, die Idee einer eigenen, nationalen „Einsatzmedaille“ zu diskutieren. Das für die Innere Führung zuständige Referat Fü S I 4 im BMVg verband mit der möglichen Einführung einer neuen Auszeichnung die Idee, den inneren Zusammenhalt der Bundeswehr zu stärken. Zugleich wollte es öffentliche Akzeptanz für das neue Aufgabenspektrum der Bundeswehr schaffen.
Tatsächlich befand sich die Bundeswehr zu dieser Zeit im tiefsten Umbruch seit ihrer Aufstellung: In den neuen Bundesländern mussten Bundeswehrstrukturen aufgebaut werden. Der Zwei-plus-Vier-Vertrag verlangte eine starke Reduzierung des Personalumfangs der deutschen Streitkräfte, die mit zahlreichen organisatorischen Veränderungen verbunden war. Finanzielle Ressourcen brachen weg, die nötig waren, um die Folgelasten der Deutschen Einheit zu bewältigen. Zudem sollte die Bundeswehr neue Aufgaben im Rahmen der internationalen Krisen- und Konfliktbewältigung übernehmen, die zunächst politisch und gesellschaftlich stark umstritten waren.
Im April 1996 stiftete Bundesverteidigungsminister Volker Rühe die Einsatzmedaille der Bundeswehr. Damit trat eine zweite militärische Auszeichnung neben das 1980 geschaffene Ehrenzeichen der Bundeswehr. Die Stiftungsgeschichte der Einsatzmedaille war geprägt von der gesellschaftspolitischen Auseinandersetzung um die Legitimität der militärischen Auslandseinsätze der Bundeswehr.
Die ersten Einsatzmedaillen wurden im Juni 1996 an deutsche Angehörige der NATO-geführten IFOR-Truppe in Bosnien-Herzegowina verliehen.







