This paper reports on the results of an experiment comparing two graphical adaptive menus for smartphones in order to improve their hierarchical navigation: “Shortcut Menu” and “Step-by-Step Menu” keep constant the actual presentation of initial menus and overlay them with a prediction window displaying the most frequently used menu items, wherever they are located in the hierarchy. In order to reach predicted items, the “Step-by-Step Menu” maintains the consistency with the initial menu through a level-by-level navigation while the “Shortcut Menu” directly moves the end user towards the predicted menu item, thus shortcutting the hierarchical navigation. Thirteen subjects performed fifty tests each on smartphones and data were collected about their item selection time and error rate. The “Step-by-Step Menu” has a positive impact on both variables, whether frequently used menu items are accurately predicted or not. The “Step-by-Step Menu” is fast, but could induce some problems when prediction is wrong.