Ranayna: You don't say which Settlers you are playing, i will just assume Settlers II, since i do not know much anymore about the first part ;)

To get a new soldier in Settlers II, you need to have a sword, a shield and a keg of beer in the same warehouse (does not need to be your headquarters)
Since wares are automatically brought to the nearest warehouse after they are produced, it is quite likely that the things you need are spread around. Just block all these items in all warehouses exept one, and then empty all those stocks that are somewhere you don't need them.

You may also still have a garrison in your Headquarters. Go to the last page in the headquarters menu and set all values to 0, if you have not done so yet. This may release some soldiers.

In Settlers II it is sadly not possible to completely remove all soldiers from a military building, so if your need is urgent, destroying buildings is the only way. But be carefull, since you will loose buildable area this way, and may destroy important buildings or streets accidentally.

Lastly, check the Military menu. Maybe you accidentally set the recruiting rate to zero. Just set the topmost bar completely full. The lowest three sliders set the amount of soldiers that will go into your huts. The far away huts should be set as low as possible (sadly the last soldier in a building will never leave), if you do not have enough soldiers to man all huts direclty at the border, you can also set the medium distance huts to the lowest, but be carefull with that. Modifying the last slider is very dangerous and opens you up for an attack, so you should not touch it, if at all posible. If your need is that dire, it might be better to restart the map.