De 256. Infanterie-Division werd op 26 augustus 1939 geformeerd als divisie binnen de 4. Welle, vanuit vervangingseenheden binnen Wehrkreis IV en Wehrkreis XIII.

Op 21 juli 1944 werd de divisie na haar inzet aan het Oostfront opgeheven.

De 256. Infanterie-Division werd op 26 augustus 1939 geformeerd binnen Wehrkreis IV als onderdeel van de 4. Welle uit onderdelen binnen Wehrkreis IV en Wehrkreis XIII.

Na opstelling in het gebied van Bohemen en Mähren, werd de divisie in november 1939 overgebracht naar de omgeving van Lippstadt en nam het op 10 mei 1940 vanuit het gebied rond Kleve deel aan de invasie van Nederland. Via Gennep trok de divisie naar Antwerpen en Nieuport, waarna het deelnam aan de strijd rond Duinkerken. Na afloop van de strijd in Frankrijk werd de divisie als bezettingsmacht in Bretagne gestationeerd.

Op 20 november 1940 werden de onderdelen Stab / Infanterie-Regiment 456, III. Bataillon / Infanterie-Regiment 456, III. Bataillon / Infanterie-Regiment 476, III. Bataillon / Infanterie-Regiment 481 en III. Abteilung / Artillerie-Regiment 256 afgegeven ter formatie van de 291. Infanterie-Division.

De vernieuwde 256. Infanterie-Division werd in februari 1941 naar Polen overgeplaatst, waarna het vanaf 22 juni 1941 deelnam aan de invasie van de Sovjet-Unie. Na een aanvankelijk opmars tot Kalinin, moest de divisie zich tijdens het Sovjet winteroffensief terugtrekken tot aan het gebied ten Oosten van Rshew. De 256. Infanterie-Division bleef op diverse locaties aan het Noordfront en bevond zich in september 1943 in de omgeving van Smolensk. Hierna volgde indeling bij het 3. Panzerarmee in de omgeving van Vitebsk.

Tijdens het Sovjet zomeroffensief van 22 juni 1944, werden de stellingen van de 256. Infanterie-Division onder de voet gelopen. De divisie werd formeel opgeheven op 21 juli 1944 nadat het vrijwel geheel was vernietigd bij Vitebsk. De restanten werden samengevoegd als Divisions-Gruppe 256 en ongedeeld bij Korps-Abteilung H.