A neural network structure search device includes a training unit which trains a neural network model with a first neural network structure using a data set for training, a first generation unit which generates analysis information indicating an importance of each of elements comprising the first neural network structure by analyzing a trained model generated from the neural network model by the training using the data set for training, an identifying unit which identifies an element in the first neural network structure whose importance is lower than a predetermined value using the generated analysis information, and a second generation unit which generates a second neural network structure based on the first neural network structure by deleting the identified element from the first neural network structure.