This study investigates how social and physical environments affect human wayfinding and locomotion behaviors in a virtual multi-level shopping mall. Participants were asked to locate a store inside the virtual building as efficiently as possible. We examined the effects of crowdedness, start floor, and trial number on wayfinding strategies, initial route choices, and locomotion behaviors. The results showed that crowdedness did not affect wayfinding strategies or initial route choices, but did affect locomotion in that participants in the high crowdedness condition were more likely to avoid crowds by moving close to the boundaries of the environment. The results also revealed that participants who started on the second floor were more likely to use the floor strategy than participants who started on the third floor, possibly because of the structure of the virtual building. These results suggest that both physical and social environments can influence multi-level indoor wayfinding.