Collaborative spatial problem solving is an important yet not thoroughly examined task. Participants navigated individually and in dyads through virtual cities of varying complexity. They only saw the environment part visible from their current location from a bird’s eye view map perspective. We recorded missed target locations, overall trajectory length and search time per person until self-indicating whole coverage. Our results show a general increase in missed locations, trajectory length, and search time with the complexity of the environment. These increases differed due to individual and collaborative search. For complex, but not for simple environments individual participants navigated shorter distances, finished earlier, but also missed more target locations than when searching the same environments in collaboration. These results indicate that in complex environments collaborative search is less error prone than individual search, but takes longer. Such initial findings will constrain future theorizing about collaborative spatial problem solving.