Cold stress adversely affects the growth and development of seedling of spring soybean. Revealing responses in seedling to cold stress at proteomic level will help us to breed cold-tolerant spring soybean cultivars. In this study, to understand the responses, a proteomic analysis on the leaves of seedlings of one cold-tolerant soybean cultivar and one cold-sensitive soybean cultivar at 5°C for different times (12 and 24 h) was performed, with some proteomic results being further validated by physiological and biochemical analysis. Our results showed that 57 protein spots were found to be significantly changed in abundance and identified by MALDI-TOF/TOF MS. All the identified proteins were found to be involved in 13 metabolic pathways and cellular processes, including photosynthesis, protein folding and assembly, cell rescue and defense, cytoskeletal proteins, transcription and translation regulation, amino acid and nitrogen metabolism, protein degradation, storage proteins, signal transduction, carbohydrate metabolism, lipid metabolism, energy metabolism, and unknown. Based on the majority of the identified cold-responsive proteins, the effect of cold stress on seedling leaves of the two spring soybean cultivars was discussed. The reason that soybean cv. Guliqing is more cold-tolerant than soybean cv. Nannong 513 was due to its more protein, lipid and polyamine biosynthesis, more effective sulfur-containing metabolite recycling, and higher photosynthetic rate, as well as less ROS production and lower protein proteolysis and energy depletion under cold stress. Such a result will provide more insights into cold stress responses and for further dissection of cold tolerance mechanisms in spring soybean.