Nanolestes krusati was named by Martin (2002). Its type specimen is PP 29/67, a tooth (left lower molar with para- and metaconid broken), and it is a 3D body fossil. Its type locality is Porto Pinheiro, Lourinha, which is in a Kimmeridgian estuary/bay marl/mudstone in the Lourinhã Formation of Portugal.