They literally couldn't be removed at a whim, yes. That's actually what makes traditional serfdom a distinctive arrangement: serfs are tied to land and must be transferred along with it when it changes hands. This would even be codified in the legal system as a right. In some cases it would be "right to subsistence" or something like it instead, meaning that the feudal could remove the serfs from some particular plot of land, but only by providing a replacement plot for them to subsist on. Courts did, in principle, enforce those rights, although of course the feudals would have a lot more opportunities to subvert them in practice (but there are still many recorded cases of serfs granted relief by medieval courts).
In Eastern Europe - and especially in Russia - serfdom began as a similar arrangement, but eventually evolved into full-fledged slavery where people could be bought and sold in and of themselves at a whim, while the original label remained for propriety reasons - basically people wanted to own slaves but didn't want to be called "slaveholders". So, a bit like "democratic people's republics" of whatever today. However, even if you take the label at face value, that arrangement still does not describe most places with serfdom.