Structural complexity is known to influence prey behaviour, mortality and population structure, but the effects on predators have received less attention. We tested whether contrasting structural complexity in two newly colonised lakes (low structural complexity lake—LSC; high structural complexity—HSC) was associated with contrasting behaviour in an aquatic apex predator, Northern pike (Esox lucius; hereafter pike) present in the lakes. Behaviour of pike was studied with whole-lake acoustic telemetry tracking, supplemented by stable isotope analysis of pike prey utilization and survey fishing data on the prey fish community. Pike displayed increased activity, space use, individual growth as well as behavioural differentiation and spent more time in open waters in the LSC lake. Despite observed differences between lakes, stable isotopes analyses indicated a high dependency on littoral food sources in both lakes. We concluded that pike in the HSC lake displayed a behaviour consistent with a prevalent ambush predation behaviour, whereas the higher activity and larger space use in the LSC lake indicated a transition to more active search behaviour. It could lead to increased prey encounter and cause better growth in the LSC lake. Our study demonstrated how differences in structural complexity mediated prominent changes in the foraging behaviour of an apex predator, which in turn may have effects on the prey community.