After the experience with Quicksilver on the Mac I found the WindowMaker dialog to run external programs a little bare. One lazy afternoon I dug in and hacked up a slight improvement (with history) using wxWidgets and Python (i.e. wxPython).
Usage is simple: you can either enter a new command in the box or use up/down to go through your history of commands. Execute the currently displayed program using either the Enter key or press OK. Cancel or pressing Escape aborts the program. Executing a modified command from the history overwrites the history entry.
The history is saved in $HOME/.history.
Download: wxrun.py