While it's true that WordPress' requirements are PHP 4.3 or higher, you will get maximum effectiveness if your hosting service supports PHP 5. I highly recommend that you enable PHP 5 support on your hosting service *before* installing WordPress. If you're already running WordPress, then you can quite likely switch to PHP 5 without any modifications, or very minimal adjustments in some cases.
Officially, PHP 4 itself is unsupported, and has been for about a year now. Unfortunately, the hosting community has been very slow to respond and upgrade. Many hosts nowadays do offer PHP 5 support, but it tends to have to be something you enable manually, or something you have to ask for.
WordPress runs demonstrably faster under PHP 5. The main reason for this is that WordPress includes a compatibility layer. Whenever it needs a PHP 5 only function that it can't find, it tries to include a backwards compatible form of that function. This backwards compatible form is inevitably slower.
Also, WordPress has begun to add support for PHP 5-only functionality as well. That is, some newer features only work with the PHP 5 code, they're simply disabled for PHP 4 code. In these cases, writing a compatibility layer was considered unnecessary or too slow. The best example of this is the Daylight Savings Time and named Timezone support.
So in the not-too-distant future, it's likely that WordPress could switch to requiring PHP 5 support entirely. Many things that are somewhat problematic with WordPress seem to sometimes magically work fine when switching to PHP 5 (notably, I've seen a lot of hosts that can do the auto-upgrade properly on PHP 5 and not on PHP 4). Many plugins are starting to require PHP 5 support right now, so it's in your best interest to switch.
The GoPHP5 initiative was started to get wider support for PHP 5, by signing on projects to drop PHP 4 support. WordPress did *not* join in on that initiative at the time, and still supports PHP 4.3 and up, but this was primarily based on statistics that show that a large percentage of WordPress users still use PHP 4.3 hosting services.
The best way you can help adoption is to make sure that you and your sites use PHP 5. With enough people using it, we can start migrating forward and using some of the newer functionality which many developers are so desperate to be able to use. :)
A codex article on how to switch is here: Switching to PHP5