To date, no study has investigated how landscape structural (visual) alterations affect navigation and thus homing success in stingless bees. We addressed this question in the Australian stingless bee Tetragonula carbonaria by performing marking, release and re-capture experiments in landscapes differing in habitat homogeneity (i.e., the proportion of elongated ground features typically considered prominent visual landmarks). We investigated how landscape affected the proportion of bees and nectar foragers returning to their hives as well as the earliest time bees and foragers returned. Undisturbed landscapes with few landmarks (that are conspicuous to the human eye) and large proportions of vegetation cover (natural forests) were classified visually/structurally homogeneous, and disturbed landscapes with many landmarks and fragmented or no extensive vegetation cover (gardens and plantations) visually/structurally heterogeneous. We found that proportions of successfully returning nectar foragers and earliest times first bees and foragers returned did not differ between landscapes. However, most bees returned in the visually/structurally most (forest) and least (garden) homogeneous landscape, suggesting that they use other than elongated ground features for navigation and that return speed is primarily driven by resource availability in a landscape.