We consider the model-checking problem for first-order logic, that is, the problem to decide for a given graph G and first-order formula whether G= .

Much work has gone into identifying classes of graphs on which this problem becomes fixed-parameter tractable, i.e. can be solved in time f()nc for some constant c and computable function f:\N\N.

It is known that if has locally bounded expansion, then the problem is indeed fixed-parameter tractable on . In this note we show that if is not nowhere dense and in addition is closed under taking sub-graphs and satisfies some effectivity conditions then FO-modelchecking is not FPT on unless FPT = AW[*]. It is still an open problem whether first-order model-checking is fixed-parameter tractable on classes of graphs which are nowhere dense, leaving a gap between our lower bound and the best currently known upper bounds