In the future, external-Human-Machine-Interfaces (eHMIs) may facilitate the communication between automated vehicles (AVs) and nearby pedestrians. The aim of this study was to investigate which messages (AVs’ intention to yield or not to yield) and perspective (does the message refer to the behavior of the vehicle or the behavior that is expected of the pedestrian) of eHMIs are understood best in terms of objective comprehension, subjective comprehensibility, and speed. Participants in an online study (N = 85) indicated whether they can safely cross or not in reaction to six different eHMI icons. Messages that tell them to cross the street were understood better and faster compared to those that instructed them not to do so. Those referring to the pedestrian were best understood objectively as well as subjectively. We advise caution regarding eHMIs that communicate that the AV is not yielding / that the pedestrian cannot cross.