Jednostki typu VIIC były kolejnym ewolucyjnym ulepszeniem najliczniej budowanych w Niemczech okrętów typu VII. Poprzednik – typ VIIB – miał zbyt mały zasięg i za mało miejsca pod pokładem, by móc zainstalować sonar. Opracowany w 1938 roku projekt nowego okrętu różnił się od poprzedniej wersji m.in. zwiększoną grubością blach kadłuba sztywnego (z 16 do 18,5 mm, co zwiększyło maksymalną głębokość zanurzenia z 200 metrów do 250–280 metrów), przedłużeniem kadłuba o 60 cm i kiosku o 30 cm oraz powiększeniem zbiorników paliwa o 5,4 m³, co poprawiło zasięg. Powiększone rozmiary pozwoliły na instalację aktywnego sonaru , uzupełniając pasywny Gruppenhorchgerät. Do zakończenia wojny do służby weszło 568 okrętów typu VIIC.
U-256 zamówiony został 23 grudnia 1939 roku. Został zbudowany w stoczni w Vegesack jako jeden z 52 okrętów typu VIIC zamówionych w tej wytwórni. U-256 otrzymał numer stoczniowy 21 (Werk 21). Stępkę okrętu położono 15 lutego 1941 roku, a zwodowany został 28 października 1941 roku.