It's hard to tell exactly when they arose, but the oldest creature I've ever heard of showing some signs of possibly having had limbs are arthropod-like fossils found dating to the late Ediacaran bearing some resemblance to the order Nectaspidida. If anything, these would have just been soft appendages hanging from the underbelly as well as antennae.
Obviously, something prior to that must have utilized protrusions of some sort from the main body to do work of one kind or another. Even unicellular creatures utilize flagella as an engineering solution to the problem of movement. Plus, limbed phyla that developed during the later Cambrian explosion didn't necessarily evolve from these earlier appendaged creatures.
But if you just imagine something like a manta ray that scours the seafloor, it's easy to see how even minor protrusions from the underbelly and forward region could prove advantageous, even if they could only be used initially for sensation and not movement. Then you can imagine the advantage it would confer for these to get longer and capable of aiding in motion.
That's speculative, though. The evolution of vertebrate limbs began in the late Cambrian and is better known since skeletons more easily fossilize. Even then, nobody really knows for certain, but Anapsids had lateral finfolds running down both sides of their bodies (just imagine pinching in the sides of a previously tubular fish). As far as I know, it's thought that true paired fins, from which other types of vertebrate limbs evolved, developed from losing segments of these folds. These were the earliest known direct prototypes of what you now walk on.