Nahhodka loodi 1941 mitme küla liitmise teel, 18. mail 1950 sai asula linnaõigused. 2004 liideti linnaga mitu alevit. Igal aastal tähistatakse 18. maid pidulikult linna päevana.