Neolithodes vinogradovi is a species of king crab whose native habitat ranges from the Arabian Sea to the Coral Sea. In the eastern Indian Ocean, one was found at a depth of 1,600 metres (5,200 ft), while in the Coral Sea, two specimens were found in the range of 1,920–2,110 metres (6,300–6,920 ft). Small differences were observed between the specimen found in the Indian Ocean and the two found in the Coral Sea.

Neolithodes vinogradovi has a has a pyriform carapace – the large male holotype's being measured at 109 mm (4.3 in) in length and 113 mm (4.4 in) in width. Long spines on its carapace's dorsal surface are arranged in a square pattern, and the surface between the spines is essentially smooth. The long spines on its chelipeds and walking legs in conjunction with the lack of smaller spines between them distinguish it from other Neolithodes.

Neolithodes vinogradovi was first described in 1988 by carcinologist Enrique Macpherson. The specific name "vinogradovi" is a dedication to the carcinologist L. G. Vinogradov.