To investigate the mechanism of laser coloring and fabrication of micro- and nano-structures fabrication on stainless steel, the influence of such laser parameters as defocusing distance, pulse energy, scanning interval, scanning speed, and repetition rate is studied. The oxide film, grating-like structure, concave and columnar protrusion are produced. The four structures lead to thin-film interference, grating diffraction effect and light trapping effect. A BP (back propagation) neural network with one hidden layer between process parameters and color parameters is established via Matlab. The training root-mean-square error of this BP neural network is 0.0078. The relative errors of hue, saturation and brightness are 23%, 10.4%, 5.6%, respectively. To a certain extent, this neural network reveals the mapping relationship between process parameters and color. The laser coloring effect can be predicted effectively with the neural network model.