Enhanced cognitive and behavioural flexibility in novel problem solving is one of the many ways in which urban animals may respond to human-made environments. Yet, the level of flexibility is expected to be affected by different urban ecological characteristics (e.g. park size, infrastructure around a park, and level of human presence/disturbance). Here, we examined this in Eurasian red squirrels that reside in urban parks with different ecological characteristics using a series of novel cognitive food-extraction tasks. We find that squirrels residing in parks with decreased naturalness and increased presence of humans have a lower innovation success rate and take longer to solve novel problems than their counterparts that reside in parks with more natural and less human presence. The more urban squirrels also took longer to solve a problem that is similar to a previously solved one (i.e. to generalise). However, surprisingly, their memory retention for solving a previously encountered problem after an extended period was better than that of their counterparts. We discuss possible cognitive mechanisms that may explain these results.