c. 1300, souder, from Old French soudier, soldier "one who serves in the army for pay," from Medieval Latin soldarius "a soldier" (source also of Spanish soldado, Italian soldato), literally "one having pay," from Late Latin soldum, extended sense of accusative of Latin solidus, name of a Roman gold coin, properly "coin of thick or solid metal," not of thin plate (see solid (adj.)).
The -l- has been regular in English since mid-14c., in imitation of Latin. Willie and Joe always say sojer in the Bill Mauldin cartoons, and this seems to mirror 16c.-17c. spellings sojar, soger, sojour. Modern French soldat is borrowed from Italian and displaced the older French word; one of many military (and other) terms picked up during the Italian Wars in early 16c.; such as alert, arsenal, colonel, infantrie, sentinel.
Old slang names for military men circa early 19c. include mud-crusher "infantryman," cat-shooter "volunteer," fly-slicer "cavalryman," jolly gravel-grinder "marine."