I've created mailbox rules but my old messages aren't moving to the mailboxes. Help! When will this happen?

The rules are for incoming messages (see the bold last sentence) - where are these "old" emails? If they are already in a certain folder, they will not move unless you do it. From the Apple Mail Help menu:

Move or copy messages

You can move or copy messages between mailboxes or folders.

Open Mail for me

• Move messages: Drag one or more messages to a mailbox in the Favorites bar or the Mail sidebar. You can also Control-click a message, choose Move To, then choose a mailbox (or use the Touch Bar).Based on your history of moving messages in Mail, the likely target mailbox can be predicted for a selected message (macOS Sierra 10.12.1 or later). For example, if you move messages from a certain person to a Travel mailbox, the command Move to “Travel” is available for other messages from that person. If a mailbox can’t be predicted, Message > Move to Predicted Mailbox is dimmed.
• Copy messages: Press and hold the Option key when you drag messages to another mailbox. Or Control-click a message, choose Copy To, then choose a mailbox.

If you have an IMAP account and are unable to move messages, it’s possible the messages contain invalid characters (typically added by a mail server) or are too large, or you exceeded the storage limits set by your email account provider.

You can use rules to automatically move certain incoming messages to specific mailboxes.

Have you tried quitting Mail and restarting it?

Rebooting your computer may help.

Make sure the rules you created do what you want. Under 'Messages' in the Menu Bar is an 'Apply Rules" command.

That many messages will take some time.

Good luck!