We asked if the structural heterogeneity of a laboratory arena differentially affected the abandonment of the plot, residence time, locomotory rate, pause duration and turning rate of adult Eriopis connexa and Hippodamia variegata (Coleoptera: Coccinellidae). We simulated an increase in heterogeneity by distributing vertically-oriented toothpicks in a circular arena: one control (without toothpicks), one uniform plot (toothpicks every 1 cm) and one random plot (randomly distributed toothpicks). No food was provided inside the arena. Coccinellids were released individually in the centre of each plot and their movement was videotaped. Fewer H. variegata adults left the plots as these become more heterogeneous. E. connexa did not discriminate between plots in their residence time, but H. variegata remained longer in the uniform and longest in the random plots. H. variegata only stayed longer than E. connexa in the random plots. This resulted because adults of H. variegata were stationary for longer periods, moved more slowly and less linearly and explored a higher number of toothpicks than adults of E. connexa in more heterogeneous environments. Thus, the physical structure of the environment differentially affects the movement patterns of insects. Eriopis connexa seems to be less sensitive to structural heterogeneity than H. variegata.