Depending on how big your potato pieces are, you should boil potatoes for 8 to 12 minutes. Stick a fork in one of the potatoes to test for doneness. The potatoes should be just fork-tender. You don't want to cook them so long that they start to fall apart.