Die Unterkünfte waren zunächst nur provisorisch hergerichtet, und auch Waffen und Uniformen waren knapp. Doch die Bedeutung dieses 2. Januar 1956 konnte auch die behelfsmäßige Ausstattung nicht schmälern: Nach heftigen politischen Debatten - sowohl im In- als auch im Ausland - rückten an diesem Tag die ersten 1.000 Rekruten der Bundeswehr in die Standorte Andernach, Nörvenich und Wilhelmshaven ein. Sie wurden in drei Lehrkompanien - Heer, Luftwaffe und Marine - einberufen, um die Aufstellung der westdeutschen Streitkräfte vorzubereiten. Noch wenige Jahre zuvor hatte sich der Bundestag gegen eine nationale Wiederbewaffnung ausgesprochen - doch Bundeskanzler Konrad Adenauer ließ sich von den massiven Widerständen nicht beirren und setzte seine 1950 begonnenen Pläne für eine neue deutsche Armee schließlich um.

Die Geburtsstunde dieser Armee hatte bereits im November 1955 geschlagen. Am 200. Geburtstag des preußischen Reformers Gerhard Johann von Scharnhorst wurden den ersten 101 Freiwilligen ihre Ernennungsurkunden ausgehändigt. Ihre Einstellung war möglich geworden, als im Juli 1955 nach langen Debatten in Bundestag und Bundesrat das Freiwilligengesetz verabschiedet worden war. Dieses Gesetz sah vor, 6.000 freiwillige Soldaten einzustellen.

Über die Bezeichnung der neu entstandenen Streitkräfte bestand zunächst Unklarheit: Während der Aushändigung der Ernennungsurkunden im November 1955 sprach Verteidigungsminister Theodor Blank die Soldaten noch mit "Meine Herren" an, bei seinem Besuch der Truppe am 20. Januar 1956 eröffnete Bundeskanzler Adenauer seine Rede mit "Soldaten der neuen Streitkräfte". In einem Gespräch mit seinem Verteidigungsminister machte Adenauer klar, dass er die Bezeichnung "Bundeswehr" dem Namen "Wehrmacht" vorziehe - schließlich sollte eine "Armee der Demokratie" entstehen, die sich in bewusster Abkehr von der nationalsozialistisch belasteten Wehrmacht verstehen sollte. Auch hier setzte Adenauer sich gegen den Trend in der Bevölkerung durch: In einer Umfrage, die das Allensbacher Institut für Meinungsforschung im gleichen Jahr im Auftrag des Bundespresseamtes durchführte, entschieden sich 35 Prozent der Befragten für die Bezeichnung "Wehrmacht", während nur jeder Vierte für den neuen Namen "Bundeswehr" plädierte.

Die endgültige Entscheidung für "Bundeswehr" fiel am 22. Februar 1956: An diesem Tag beriet der Sicherheitsausschuss des Deutschen Bundestages über das "Soldatengesetz" und stimmte über den Namen der Streitkräfte ab.

War die Bezeichnung der Armee zunächst umstritten, bestand von Anfang an Klarheit über die Aufgaben der neuen deutschen Soldaten. Bei seinem Besuch der Truppe in Andernach im Januar 1956 führte Kanzler Adenauer aus, das deutsche Volk sehe in den Soldaten "die lebendige Verkörperung seines Willens, seinen Teil beizutragen zur Verteidigung der Gemeinschaft freier Völker, der wir heute wieder mit gleichen Rechten und Pflichten wie die anderen angehören". Das einzige Ziel der deutschen Wiederbewaffnung sei es, "zur Erhaltung des Friedens beizutragen". Dieses Ziel sei erreicht, wenn "die gemeinsame potenzielle Abwehrkraft der Verbündeten zu jedem Zeitpunkt ein zu großes Risiko für jeden Angreifer bedeutet. In einer solchen militärischen Stärke, die lediglich für unsere Verteidigung ausreicht, kann niemand eine Bedrohung erblicken." Adenauer sah in den neuen Streitkräften eine große Chance für die Zukunft: "Soldaten! Sie stehen vor einer Aufgabe, die durch manche Schatten der Vergangenheit und Probleme der Gegenwart besonders schwierig ist. Die zeitliche Lücke von zehn Jahren bedeutet zugleich

die einmalige Möglichkeit zu neuem Beginn, wie auch die Verpflichtung, in unermüdlicher Arbeit Versäumtes nachzuholen." Die Angehörigen der Streitkräfte seien "Kinder dieses Volkes, dessen Geist und Lebensart auch ihre Persönlichkeit geprägt hat" - sie unterstünden "wie jeder andere Zweig der staatlichen Exekutive dem Vorrang der politischen Führung".

Diese politische Führung wurde im März 1956 im so genannten Wehrergänzungsgesetz festgeschrieben: Danach liegt die Befehls- und Kommandogewalt über die Bundeswehr beim Verteidigungsminister und geht im Verteidigungsfall auf den Bundeskanzler über.

Aus der Freiwilligenarmee wurde schnell eine Wehrpflichtarmee: Am 7. Juli 1956 verabschiedete der Bundestag das "Gesetz zur Einführung der allgemeinen Wehrpflicht". Von nun an mussten alle jungen Männer, die diensttauglich waren, ihren Dienst in den Streitkräften verrichten.